題意：求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<=1e12 , 所以回報 long long！那么對于大于1e9的數我做了大數乘法的處理！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 void fun(int a[], long long b, int &l){//將一個數進行拆分放到數組中！ 7 while(b){ 8 a[l++] = b%10; 9 b/=10; 10 } 11 } 12 13 14 int a[30], b[30], c[30]; 15 int la, lb; 16 17 void cal(){ 18 memset(c, 0, sizeof(c)); 19 for(int i=0; i<la; ++i) 20 for(int j=0; j<lb; ++j) 21 c[i+j] += a[i]*b[j]; 22 int k=0; 23 int len = la+lb-1; 24 for(int i=0; i<len; ++i){ 25 c[i]+=k; 26 k = c[i]/10; 27 c[i]%=10; 28 } 29 if(k>0) c[len++] = k; 30 k = 2; 31 for(int i=0; i<len; ++i){ 32 c[i]+=k; 33 k = c[i]/10; 34 c[i]%=10; 35 } 36 if(k>0) c[len++] = k; 37 38 for(int i = len-1; i>=0; --i) 39 printf("%d", c[i]); 40 printf("\n"); 41 } 42 43 int main(){ 44 long long n; 45 int t, cnt=0; 46 scanf("%d", &t); 47 while(t--){ 48 scanf("%I64d", &n); 49 printf("Case #%d: ", ++cnt); 50 if(n <= 1e9) 51 printf("%I64d\n", (8*n+1)*(n-1)+2); 52 else{ 53 long long x = 8*n+1; 54 long long y = n-1; 55 la=lb=0; 56 fun(a, x, la); 57 fun(b, y, lb); 58 cal(); 59 } 60 } 61 return 0; 62 }
本文轉自 小眼兒 博客園博客，原文鏈接：http://www.cnblogs.com/hujunzheng/p/3997036.html，如需轉載請自行聯系原作者
