首页 > 代码库 > hdu 1014.Uniform Generator 解题报告

hdu 1014.Uniform Generator 解题报告

题目链接: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 列,记得输出答案后要输出两个空行!

  

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6  7 int main() 8 { 9     int step, mod;10     while (scanf("%d%d", &step, &mod) != EOF)11     {12         int d = 0;13         int i = 1;14         for ( ; d = (d+step)%mod; i++)15             ;16         printf("%10d%10d    %s\n\n", step, mod, i == mod ? "Good Choice" : "Bad Choice");17     }18     return 0;19 }

 

  《短码之美》说可以使用,线性同余法来做 seed(x+1) = [A*seed(x) + STEP] % MOD ,此题就是A = 1。最后其实就是判断互质,不过有一些看得不太懂,而且感觉代码写出来非常规,虽然更短但可读性不太高就.....

hdu 1014.Uniform Generator 解题报告