#include <iostream>
using namespace std;
int a,b,s[100];
struct Pair
{
int x;
int y;
}res[50];
int main()
{
int n,i,j,k;
bool flag=false;
res[0].x=res[0].y=1;
while(cin>>a>>b>>n)
{
if(!(a||b||n))return 0;
for(i=1;i<50;++i)
{
res[i].x=res[i-1].y;
res[i].y=(a*res[i-1].y+b*res[i-1].x)%7;
for(j=0;j<i-1;++j)//…………………………注意这里循环上限是i-1，这样可以排除三个连续相等的情况。就是把循环节为1的看成2.
{
if(res[j].x==res[i].x&&res[j].y==res[i].y)
{
flag=true;
break;
}
}
if(flag)break;
}//一个循环找出循环节大小
flag=false;//……………………注意把标志还原
if(n<=j)cout<<res[n].x<<endl;//未进入循环时
else
{
if((n-j)%(i-j)==0)k=i-1;
else k=(n-j)%(i-j)+j-1;//这个式子改了很长时间，总是会出现问题。这是最终的形式
cout<<res[k].x<<endl;
}
}
return 0;
}
提交了七次终于给过了。是道数论的简单题，不过应该用不到什么高深的知识，关键是找出循环节。因为对于1000000000的大小，如果不找规律的话无论如何也要超时的。分析一下，每个数仅取决于它前面的两个，所以如果出现了相同的数对，则必出现循环。而且，每个数都是0~6之间的一个，可知不同的数对只有7*7=49个，那么只要计算出前50个数，则其中必有相同的两对数出现。上代码。AC之后我想知道循环是不是总是从最前面两个数开始，于是简单写了一个程序，遍历了所有的a,b(易知它们也只有49种组合)，下面是我得到的结果：
a b j i i-j
0 0 2 4 2
0 1 0 2 2
0 2 0 6 6
0 3 0 12 12
0 4 0 6 6
0 5 0 12 12
0 6 0 4 4
1 0 0 2 2
1 1 0 16 16
1 2 0 6 6
1 3 0 24 24
1 4 0 48 48
1 5 0 21 21
1 6 0 6 6
2 0 1 4 3
2 1 0 6 6
2 2 0 48 48
2 3 0 6 6
2 4 0 48 48
2 5 0 24 24
2 6 0 2 2
3 0 1 7 6
3 1 0 16 16
3 2 0 48 48
3 3 0 42 42
3 4 0 6 6
3 5 0 2 2
3 6 0 8 8
4 0 1 4 3
4 1 0 16 16
4 2 0 48 48
4 3 0 21 21
4 4 0 2 2
4 5 0 6 6
4 6 0 8 8
5 0 1 7 6
5 1 0 6 6
5 2 0 48 48
5 3 0 2 2
5 4 0 48 48
5 5 0 24 24
5 6 0 14 14
6 0 1 3 2
6 1 0 16 16
6 2 0 2 2
6 3 0 24 24
6 4 0 48 48
6 5 0 42 42
6 6 0 3 3
可见当a,b都是7的倍数时，循环从第三个数开始（以后都是0）；当a,b中只有一个是7的倍数时，循环从第二个数开始（1,0、0,1的情况比较特殊，因为跟开始的1,1重复了所以可以认为是从第一个数开始）；当a,b都不是7的倍数是，循环从第一个数开始。可见还是从第一个数开始循环的多。循环节也有长有短，比如当a=1,b=4时一直到第49个数才出现循环。
posted on 2010-11-18 17:00
cometrue 阅读(1496)
评论(2) 编辑 收藏 引用