摘取于http://blog.csdn.net/kenden23/article/details/37519883；

找到規(guī)律之后本題就是水題了，不過(guò)找規(guī)律也不太容易的，證明這個(gè)規(guī)律成立更加不容易。

本題就是求step和mod如果GCD（最大公約數(shù)位1）那么就是Good Choice，否則為Bad Choice

為什么這個(gè)結(jié)論成立呢？

因?yàn)楫?dāng)GCD(step, mod) == 1的時(shí)候，那么第一次得到序列：x0, x0 + step, x0 + step…… 那么mod之后，必然下一次重復(fù)出現(xiàn)比x0大的數(shù)必然是x0+1，為什么呢？

因?yàn)?x0 + n*step) % mod； 且不需要考慮x0 % mod的值為多少，因?yàn)槲覀兿胫赖谝淮伪葂0大的數(shù)是多少，那么就看n*step%mod會(huì)是多少了，因?yàn)镚CD(step, mod) == 1，那么n*step%mod必然是等于1，故此第一次重復(fù)出現(xiàn)比x0大的數(shù)必然是x0+1，那么第二次出現(xiàn)比x0大的數(shù)必然是x0+2，以此類(lèi)推，就可得到必然會(huì)出現(xiàn)所有0到mod-1的數(shù)，然后才會(huì)重復(fù)出現(xiàn)x0.

當(dāng)GCD(step, mod) != 1的時(shí)候，可以推出肯定跨過(guò)某些數(shù)了，這里不推了。

然后可以擴(kuò)展這個(gè)結(jié)論，比如如果使用函數(shù) x(n) = (x(n-1) * a + b)%mod；增加了乘法因子a，和步長(zhǎng)b了；

那么如果是Good Choice，就必然需要GCD(a, mod) == 1，而且GCD(b, mod) == 1；

（另外的證明）

對(duì)于mod n域中的任意數(shù)a，若有g(shù)cd(m,n)=1，則m為該域的生成元，使得a+km可以為域中任意數(shù).

證明十分簡(jiǎn)單，若gcd(m,n)=1，則lcm(m,n)=m*n,則對(duì)于a的mod n運(yùn)算,需要n次的計(jì)算才能回到a，期間必遍歷該域中所有數(shù)！

#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> #include<map> using namespace std; #define ll __int64 #define mod 1000000007 int scan() {int res = 0 , ch ;while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) ){if( ch == EOF ) return 1 << 30 ;}res = ch - '0' ;while( ( ch = getchar() ) >= '0' && ch <= '9' )res = res * 10 + ( ch - '0' ) ;return res ; } int gcd(int x,int y) {return x%y?gcd(y,x%y):y; } int main() {int x,y,z,i,t;while(~scanf("%d%d",&x,&y)){printf("%10d%10d",x,y);if(gcd(x,y)==1)printf(" Good Choice\n");//４個(gè)空格,pe多次elseprintf(" Bad Choice\n");printf("\n");}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/jhz033/p/5330326.html

總結(jié)

以上是生活随笔為你收集整理的hdu 1014 Uniform Generator 数论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。