1605: 数字序列
时间限制: 1 Sec 内存限制: 60 MB提交: 778 解决: 179
[提交][状态][讨论版][命题人:541307010108]
题目描述
一个数列的定义如下：
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A和B，你要求出f(n).
输入
输入包含多个测试案例。每个测试用例包含3个整数A，B和n在一行（1＜＝A，B≤1000，1≤n≤100000000）。
当输入三个0表示结束
输出
对于每个测试案例，输出f(n)，单独占一行。
样例输入
1 1 3
1 2 10
0 0 0样例输出
2
5
在一定的运算后会循环,所以只要算出多少个数字循环一次即可
#include<stdio.h>
#define N 60
int f[N];
int main()
{
int a,b,n,i,j,sum,ans;
while(scanf("%d%d%d",&a,&b,&n)!=EOF)
{
sum=0;
if(a==0&&b==0&&n==0)
break;
f[1]=1;f[2]=1;
for(i=3;i<N;i++)
f[i]=(a*f[i-1]+b*f[i-2])%7;
if(n<N)
printf("%d
",f[n]);
else
{
ans=0;
for(i=1;i<N-1;i++)
{
for(j=i+1;j<N-1;j++)
if(f[j]==f[i]&&f[j+1]==f[i+1])
{
sum=j-i;
ans=1;
break;
}
if(ans==1)
break;
}
i=i-1;
n=(n-i)%sum;
if(n)
printf("%d
",f[n+i]);
else
printf("%d
",f[i+sum]);
}
}
return 0;
}