hdu 1014 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1014
乍看题目，如果通过暴力方法求出每一次每一个序列，然后在验证是否是good choice或者bad，但是这么做就很麻烦，超过运行时间。 既然这么做不行，就试着将问题转化 seed(x+1) = [seed(x) + STEP] % MOD
seed(0) = 0 所以seed[]的值都是由STEP和MOD来决定，如果S和M为good choice则seed[]的值为0~MOD-1，即要求最后能够出现循环序列，并且为0~MOD-1，所以要求每次的生成值和MOD互质，代码如下 [cpp] view plaincopy

1. #include  
2. int gcd(int a,int b)  
3. {  
4.     if(a%b==0)  
5.         return b;  
6.     else  
7.         return gcd(b,a%b);  
8. }  
9. int main()  
10. {  
11.     int i,j,k,m,n,s;  
12.     while(scanf("%d%d",&s,&m)!=EOF)  
13.     {  
14.         if(gcd(s,m)!=1)  
15.             printf("%10d%10d    Bad Choice ",s,m);  
16.         else  
17.             printf("%10d%10d    Good Choice ",s,m);  
18.     }  
19.     return 0;  
20. }  
21.         

补充知识： 循环群 循环群生成元 对于mod n域中的任意数a，若有gcd(m,n)=1，则m为该域的生成元，使得a+km可以为域中任意数. 证明十分简单，若gcd(m,n)=1，则lcm(m,n)=m*n,则对于a的mod n运算,需要n次的计算才能回到a，期间必遍历该域中所有数！gcd(m,n)为最大公约数