随笔-6  评论-2  文章-0  trackbacks-0
#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 阅读(1494) 评论(2)  编辑 收藏 引用

评论:
# re: hdoj_1005_Number Sequence 2010-11-18 17:14 | 威士忌
int main()
{
int A,B,n,i,j,num,m;
int a[1000];
while(scanf("%d %d %d",&A,&B,&n)!=EOF)
{
if(A==0 && B==0 && n==0)
break;
a[1]=1;a[2]=1;
for(i=3;i<50;i++)
a[i]=( A * a[i - 1] + B * a[i - 2]) % 7;
m=1;
for(j=3;j<50;j++)
if(a[j]==1 && a[j-1]==1)
break;
j-=2;
num=n%j;
if(num==0)
printf("%d\n",a[j]);
else
printf("%d\n",a[num]);
}
return 0;
}  回复  更多评论
  
# re: hdoj_1005_Number Sequence 2012-08-14 08:38 | curtius
@威士忌
你的代码很清晰
这么多版本中 你的好理解  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理