题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1014
题目意思:给出 STEP 和 MOD,然后根据这个公式:seed(x+1) = [seed(x) + STEP] % MOD,问是否在一个周期里可以产生 0 ~ mod-1 的数。可以的话输出 "Good Choice", 否则输出 "Bad Choice"。
好久以前留下来的问题了,以前觉得题目意思又长,以为是很难的题目......今天看《短码之美》看到这题,干脆做了。纸老虎一只!
可以初始化 seed 为 0,然后用公式,次数初始化 i = 1,因为初始化的 seed = 0 已经占有了一次。最后判断次数是否等于 MOD,是的话代表 0 ~ MOD-1 的数都出现过,输出 "Good Choice"
最后就是格式问题了,STEP 和 MOD 各占有10 列,分别为 1~10 和 11 ~ 20。字符串开头在25 列,记得输出答案后要输出两个空行!
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; int main()
{
int step, mod;
while (scanf("%d%d", &step, &mod) != EOF)
{
int d = ;
int i = ;
for ( ; d = (d+step)%mod; i++)
;
printf("%10d%10d %s\n\n", step, mod, i == mod ? "Good Choice" : "Bad Choice");
}
return ;
}
《短码之美》说可以使用,线性同余法来做 seed(x+1) = [A*seed(x) + STEP] % MOD ,此题就是A = 1。最后其实就是判断互质,不过有一些看得不太懂,而且感觉代码写出来非常规,虽然更短但可读性不太高就.....