杭電OJ 1005：Number Sequence

這個題目如果使用數組或者遞歸都會爆棧，注意到題目中的數都是對7取餘，是以相鄰的兩個數的組合最多有49中，是以最多49次循環就會從頭開始循環，這是就可以不用繼續執行了，然後将n對i取餘，根據餘數就可以得到結果。

C++代碼：

#include<stdio.h>
const int N=55;
int dp[N];
int getRes(int A,int B,int n){
	if(n==1||n==2)
		return 1;
	else{
		dp[1]=1;dp[2]=1;int i;
		for(i=3;i<=N;i++){
			dp[i]=(A*dp[i-1]+B*dp[i-2])%7;
			if(dp[i]==dp[i-1]&&dp[i-1]==1)
				break;
		}
		i-=2;
		n=n%i;
		if(n)
			return dp[n];
		else
			return dp[i];
	}
}
int main(){
	int a,b,n;
	while(scanf("%d%d%d",&a,&b,&n)!=EOF){
		if(a==0&&b==0&&n==0)
			return 0;
		printf("%d\n",getRes(a,b,n));
	}
	return 0;
}