hdu-1715 （大数加法模板）

大菲波数

Time Limit: 1000/1000 MS (Java/Others) ? ?Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11568 ? ?Accepted Submission(s): 3928

Problem Description
Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
?
Input
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
?
Output
输出为N行，每行为对应的f(Pi)。
?
Sample Input
5
1
2
3
4
5
?
Sample Output
1
1
2
3

5

#include<iostream>
#include<string>
using namespace std;
void fs(string a,string b,string &c)
{
	int la=a.length()-1;
	int lb=b.length()-1;
	int k=0,x;
	while(la>=0||lb>=0)
	{
		if(la>=0&&lb>=0){
			c=char((a[la]+b[lb]-96+k)%10+48)+c;
			k=(a[la]+b[lb]-96+k)/10;
			la--;lb--;
		}
		else if(la>=0){
			c=char((a[la]-48+k)%10+48)+c;
			k=(a[la]+k-48)/10;
			la--;
		}
		else if(la>=0){
			c=char((b[lb]-48+k)%10+48)+c;
			k=(b[lb]+k-48)/10;
			lb--;
		}
	}
	if(k!=0) c=char(k+48)+c;
}
int main()
{
	int n,m;
	string f[1001];
	f[1]="1";
	f[2]="1";
	cin>>n;
	for(int i=3;i<=1000;i++)
		fs(f[i-1],f[i-2],f[i]);
	while(n--)
	{
		cin>>m;
		cout<<f[m]<<endl;
	}
	return 0;
}