Description

    ACM 程序设计竞赛是一项激励人心的竞赛，除了考验大家的编程功底，更多的是考验大家的思维以
及数学运算能力。开赛前15分钟，我们华农的某队开始了以下对话：
ipc：“我们玩接龙热一下身吧！免得一会没睡醒。”
Arokenda：“好啊！没问题！怎么玩？”
ipc：“我先写两个数，然后你我轮流接着已经写好的数列继续写数，每人写1 个数。接龙的规则就是，
下一个数是前两个数的和。”
Arokenda：“这还不简单！不就是Fibonacci数列嘛。绝对秒杀啦！”
    此时，ipc 开始写数：1、3。居然不是Fibonacci 数列！下一个就是4 啦！接着数列成型了：1、3、
4、7、11、18……一直写了N 项，ipc 觉得热身还不够。于是他忽然说了句：“求前N 项和怎么样？”两
个人顿时“卡”了一下……
若ipc写出数列的前两项以及项数，你能算出来吗？

输入格式

输入一个整数T(T<=20)，表示ipc写了T个数列。
接下来T行， 每行三个整数， 分别为a1,a2,n ， 分别表示该数列的前两项和项数。其中0<a1,a2,n<=1000

输出格式

每组数据输出一行，该数列的前n项和sum(n)。

输入样例

输出样例

2582
143
286

提示

来源

朱伟琛

作者

admin

求数列的前N项和，这道题里可以直接暴力累加，唯一考到的就是高精度加法；不过这里用到的高精度函数写的并不好。。。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 void big_add(char*str1,char*str2,char*strsum);
 7 int main()
 8 {
 9     int t,n,i;
10     scanf("%d",&t);
11     while(t--)
12     {
13         char strsum[100000];
14         char str1[100000],str2[100000],strtemp[100000]; char*temp1=NULL,*temp2=NULL,*sum=strsum;
15         scanf("%s %s %d",str1,str2,&n);
16         temp1=str1; temp2=str2;
17         char*str_temp=strtemp;
18         big_add(temp1,temp2,sum);
19         if(n==1)
20         {
21             printf("%s
",str1);
22             continue;
23         }
24         if(n==2)
25         {
26             printf("%s
",sum);
27             continue;
28         }
29         //
30         for(i=3;i<=n;i++)
31         {
32            big_add(temp1,temp2,str_temp);
33            big_add(sum,str_temp,sum);
34            strcpy(str1,str2); strcpy(str2,strtemp);
35 
36         }
37         printf("%s
",strsum);
38     }
39     return 0;
40 }
41 void big_add(char*str1,char*str2,char*tsum)
42 {
43 
44     int sum[100000]={0}; int i,j,k=0;
45     i=strlen(str1); j=strlen(str2);
46     i--;j--;
47     for(;i>=0&&j>=0;i--,j--)
48     {
49         sum[k++]+=str1[i]-'0'+str2[j]-'0';
50     }
51     //
52     while(i>=0)
53         sum[k++]+=str1[i--]-'0';
54     while(j>=0)
55         sum[k++]+=str2[j--]-'0';
56     for(i=0;i<k;i++)
57         if(sum[i]>=10)
58         {
59             sum[i]-=10;
60             sum[i+1]++;
61         }
62     //
63     if(sum[k]==0) k--;
64     j=0;
65     for(i=k;i>=0;i--)
66     {
67         tsum[j++]=sum[i]+'0';
68     }
69     tsum[j]='';
70 
71 }