hdu----(5047)Sawtooth(大数相乘+数学推导)

Sawtooth

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 422 Accepted Submission(s): 134

Problem Description

Think about a plane:

● One straight line can divide a plane into two regions.
● Two lines can divide a plane into at most four regions.
● Three lines can divide a plane into at most seven regions.
● And so on...

Now we have some figure constructed with two parallel rays in the same direction, joined by two straight segments. It looks like a character “M”. You are given N such “M”s. What is the maximum number of regions that these “M”s can divide a plane ?

Input

The first line of the input is T (1 ≤ T ≤ 100000), which stands for the number of test cases you need to solve.

Each case contains one single non-negative integer, indicating number of “M”s. (0 ≤ N ≤ 10¹²)

Output

For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then an integer that is the maximum number of regions N the “M” figures can divide.

Sample Input

2
1
2

Sample Output

Case #1: 2
Case #2: 19

Source

2014 ACM/ICPC Asia Regional Shanghai Online

其实题目已经很清楚的告知我们是有线条分平面引申而来的了....

对于线条分平面

0 1

1 1 +1

2 1+1 +2

3 1+1 +2+3

4 1+1 +2+3+4

............

n 1+n(n+1)/2;

那么对于一个m型号的模型，其实我们可以将其视其为四条线段组合而成，这样这个公式就变为：

4n*(4n+1)/2 +1 ---->显然得到的答案有余坠，我

0 1

1 11 2 9

2 37 19 9*2

......

推到得到：

4n*(4n+1)/2 +1 -8*n----> 8n^2-7n+1

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 char aa[50],bb[50];
 4 int ans[50];
 5 int mul( char *a, char *b, int temp[])
 6 {
 7 
 8     int i,j,la,lb,l;
 9     la=strlen(a);
10     lb=strlen(b);
11 
12     for ( i=0;i<la+lb;i++ )
13         temp[i]=0;
14     for ( i=0;i<=la-1;i++ ) {
15           l=i;
16         for ( j=0;j<=lb-1;j++ ) {
17             temp[l]=(b[j]-'0')*(a[i]-'0')+temp[l];
18             l++;
19         }
20     }
21     while ( temp[l]==0 )
22         l--;
23     for ( i=0;i<=l;i++ ) {
24         temp[i+1]+=temp[i]/10;
25         temp[i]=temp[i]%10;
26     }
27     if ( temp[l+1]!=0 )
28         l++;
29 
30     while ( temp[l]/10!=0 ) {
31         temp[l+1]+=temp[l]/10;
32         temp[l]=temp[l]%10;
33         l++;
34     }
35     if ( temp[l]==0 )
36         l--;
37     return l;
38 }
39 void cal(__int64 a,char *str)
40 {
41     int i=0;
42     while(a>0)
43     {
44      str[i++]=(a%10)+'0';
45      a/=10;
46     }
47 }
48 int main()
49 {
50     int cas;
51     __int64 n;
52     scanf("%d",&cas);
53     for(int i=1;i<=cas;i++)
54     {
55       scanf("%I64d",&n);
56       printf("Case #%d: ",i);
57       if(n==0)printf("1
");
58       else
59       {
60       memset(aa,'',sizeof(aa));
61       memset(bb,'',sizeof(bb));
62       memset(ans,0,sizeof(ans));
63       //,(8*n-7)*n+1
64       cal(8*n-7,aa);
65       cal(n,bb);
66       int len=mul(aa,bb,ans);
67        ans[0]++;
68        int c=0;
69      for(int j=0;j<=len;j++)
70      {
71          ans[j]+=c;
72        if(ans[j]>9)
73         {
74           c=ans[j]/10;
75           ans[j]%=10;
76         }
77      }
78       if(c>0)
79         printf("%d",c);
80       for(int j=len;j>=0;j--)
81         printf("%d",ans[j]);
82     printf("
");
83     }
84     }
85  return 0;
86 }

View Code