题意:求n个'M'型的折线将一个平面分成的最多的面数!
思路:我们都知道n条直线将一个平面分成的最多平面数是 An = An-1 + n+1
也就是f(n) = (n*n + n +2)/2
对于一个'M'型的折线呢?它有四条线,但是由于三个顶点的关系导致划分的平面
的数目减少了9个!所以有递推公式 f(n) = (m*m + m + 2)/2 - 9*n; m = 4*n
最后 f(n) = (8*n+1)*(n-1)+2)
思路:我们都知道n条直线将一个平面分成的最多平面数是 An = An-1 + n+1
也就是f(n) = (n*n + n +2)/2
对于一个'M'型的折线呢?它有四条线,但是由于三个顶点的关系导致划分的平面
的数目减少了9个!所以有递推公式 f(n) = (m*m + m + 2)/2 - 9*n; m = 4*n
最后 f(n) = (8*n+1)*(n-1)+2)
由于 n<=1e12 , 所以回报 long long!那么对于大于1e9的数我做了大数乘法的处理!
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void fun(int a[], long long b, int &l){//将一个数进行拆分放到数组中!
while(b){
a[l++] = b%10;
b/=10;
}
}
int a[30], b[30], c[30];
int la, lb;
void cal(){
memset(c, 0, sizeof(c));
for(int i=0; i<la; ++i)
for(int j=0; j<lb; ++j)
c[i+j] += a[i]*b[j];
int k=0;
int len = la+lb-1;
for(int i=0; i<len; ++i){
c[i]+=k;
k = c[i]/10;
c[i]%=10;
}
if(k>0) c[len++] = k;
k = 2;
for(int i=0; i<len; ++i){
c[i]+=k;
k = c[i]/10;
c[i]%=10;
}
if(k>0) c[len++] = k;
for(int i = len-1; i>=0; --i)
printf("%d", c[i]);
printf("\n");
}
int main(){
long long n;
int t, cnt=0;
scanf("%d", &t);
while(t--){
scanf("%I64d", &n);
printf("Case #%d: ", ++cnt);
if(n <= 1e9)
printf("%I64d\n", (8*n+1)*(n-1)+2);
else{
long long x = 8*n+1;
long long y = n-1;
la=lb=0;
fun(a, x, la);
fun(b, y, lb);
cal();
}
}
return 0;
}