#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)//…………………………注意這里循環(huán)上限是i-1，這樣可以排除三個(gè)連續(xù)相等的情況。就是把循環(huán)節(jié)為1的看成2.
{
if(res[j].x==res[i].x&&res[j].y==res[i].y)
{
flag=true;
break;
}
}
if(flag)break;
}//一個(gè)循環(huán)找出循環(huán)節(jié)大小
flag=false;//……………………注意把標(biāo)志還原
if(n<=j)cout<<res[n].x<<endl;//未進(jìn)入循環(huán)時(shí)
else
{
if((n-j)%(i-j)==0)k=i-1;
else k=(n-j)%(i-j)+j-1;//這個(gè)式子改了很長(zhǎng)時(shí)間，總是會(huì)出現(xiàn)問(wèn)題。這是最終的形式
cout<<res[k].x<<endl;
}
}
return 0;
}
提交了七次終于給過(guò)了。是道數(shù)論的簡(jiǎn)單題，不過(guò)應(yīng)該用不到什么高深的知識(shí)，關(guān)鍵是找出循環(huán)節(jié)。因?yàn)閷?duì)于1000000000的大小，如果不找規(guī)律的話無(wú)論如何也要超時(shí)的。分析一下，每個(gè)數(shù)僅取決于它前面的兩個(gè)，所以如果出現(xiàn)了相同的數(shù)對(duì)，則必出現(xiàn)循環(huán)。而且，每個(gè)數(shù)都是0~6之間的一個(gè)，可知不同的數(shù)對(duì)只有7*7=49個(gè)，那么只要計(jì)算出前50個(gè)數(shù)，則其中必有相同的兩對(duì)數(shù)出現(xiàn)。上代碼。AC之后我想知道循環(huán)是不是總是從最前面兩個(gè)數(shù)開(kāi)始，于是簡(jiǎn)單寫(xiě)了一個(gè)程序，遍歷了所有的a,b(易知它們也只有49種組合)，下面是我得到的結(jié)果：
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
可見(jiàn)當(dāng)a,b都是7的倍數(shù)時(shí)，循環(huán)從第三個(gè)數(shù)開(kāi)始（以后都是0）；當(dāng)a,b中只有一個(gè)是7的倍數(shù)時(shí)，循環(huán)從第二個(gè)數(shù)開(kāi)始（1,0、0,1的情況比較特殊，因?yàn)楦_(kāi)始的1,1重復(fù)了所以可以認(rèn)為是從第一個(gè)數(shù)開(kāi)始）；當(dāng)a,b都不是7的倍數(shù)是，循環(huán)從第一個(gè)數(shù)開(kāi)始?？梢?jiàn)還是從第一個(gè)數(shù)開(kāi)始循環(huán)的多。循環(huán)節(jié)也有長(zhǎng)有短，比如當(dāng)a=1,b=4時(shí)一直到第49個(gè)數(shù)才出現(xiàn)循環(huán)。
posted on 2010-11-18 17:00
cometrue 閱讀(1540)
評(píng)論(2) 編輯 收藏 引用