这道题要求判断STEP和MOD的值是"Good Choice"还是"Bad Choice"。
观察分析后可以发现step和mod互质时是Good Choice,否则为Bad Choice。下面证明:
我们可以这样分析:
因为
所以 每次产生的seed只与上一个seed,STEP, MOD有关。当STEP, MOD的值确定时,假定第一个seed的值为0,则所得的seed序列是确定的。
该序列为:
0, 1*step%mod, 2*step%mod, 3*step%mod, ......, (mod-1)*step%mod, ......(往后将重复出现前mod个seed的序列)
故而 如果STEP和MOD 是Good Choice,则在前mod个序列中0~mod-1均出现一次。
而此时 若step与mod并不互质,则存在a>1 并且 a | step 且 a | mod。
那么令 sa = step / a, ma = mod / a, 原seed序列将变成:
0,(1*sa%ma)*a, (2*sa%ma)*a, (3*sa%ma)*a, ... ..., ((mod-1)*sa%ma)*a, ......
由于0, 1*sa%ma, 2*sa%ma, 3*sa%ma, ... ... , (mod-1)*sa%ma, ........中至多有ma个不同的值, 新序列中也至多有ma个不同的值。而ma<mod,故新序列中不同的值少于mod个,必定无法0~mod-1均出现一次。
故step与mod不互质时,STEP和MOD是Bad Choice。只有step与mod互质时才是Good Choice。
因而本题只需判断step与mod是否互质即可,这可以用两者的最大公约数是否为1来判断。
代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> using namespace std; int gcd(int a, int b) { if(b==0) return a; return gcd(b,a%b); } bool is_co_prime(int a, int b) { if(gcd(a,b)==1) return true; else return false; } int main() { int step,mod; while(cin >> step >> mod) { printf("%10d%10d ",step,mod); if(is_co_prime(step,mod)) printf("Good Choice\n\n"); else printf("Bad Choice\n\n"); } return 0; }