题目描述

Computer simulations often require random numbers. One way to generate pseudo-random numbers is via a function of the form
（计算机模拟通常需要随机数。产生伪随机数的一种方法是通过形式seed(x+1) = [seed(x) + STEP] % MOD的函数）
where '%' is the modulus operator. （其中'％'是模数运算符。）

Such a function will generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this effect, selecting the STEP and MOD values carefully can result in a uniform distribution of all values between (and including) 0 and MOD-1.
（这样的函数将生成0和MOD-1之间的伪随机数（种子）。这种形式的功能的一个问题是它们总是一遍又一遍地生成相同的模式。为了最大限度地减少这种影响，仔细选择STEP和MOD值可以使0（包括）和MOD-1之间的所有值均匀分布。）

For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle.（STEP = 3，MOD = 5，则该函数将在重复周期中生成一系列伪随机数0,3,1,4,2。）

If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and MOD-1.
（STEP = 15且MOD = 20，则函数生成序列0,15,10,5。这是很差的STEP和MOD选择，因为没有初始种子将生成0和MOD-1中的所有数字。）

Your program will determine if choices of STEP and MOD will generate a uniform distribution of pseudo-random numbers.
（您的程序将确定STEP和MOD的选择是否会产生伪随机数的均匀分布。 ）

理解题意：

直接找到题目中两个样例，可以得出初始seed（x）= 0，后一个seed（x+1）是seed（x）加step再对mod取模的值，判定step和mod是否为好选择的关键就是看有限次计算后0和mod-1之间的数字是否在结果中都出现过。

Input
Each line of input will contain a pair of integers for STEP and MOD in that order (1 <= STEP, MOD <= 100000).
（每行输入将按顺序包含一对STEP和MOD的整数（1 <= STEP，MOD <= 100000））

Output
For each line of input, your program should print the STEP value right- justified in columns 1 through 10, the MOD value right-justified in columns 11 through 20 and either "Good Choice" or "Bad Choice" left-justified starting in column 25. The "Good Choice" message should be printed when the selection of STEP and MOD will generate all the numbers between and including 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message "Bad Choice". After each output test set, your program should print exactly one blank line.
（对于每行输入，程序应在第1列到第10列中右对齐地打印STEP值，在第11到第20列中右对齐MOD值，在列中开始左对齐“Good Choice”或“Bad Choice” 25.当生成MOD编号时，选择STEP和MOD将生成0和MOD-1之间的所有数字时，应打印“Good Choice”消息。否则，您的程序应该打印消息“Bad Choice”。在每个输出测试集之后，程序应该只打印一个空白行。）

Sample Input

3 5
15 20
63923 99999

Sample Output

         3         5    Good Choice

        15        20    Bad Choice

     63923     99999    Good Choice

这道题因为分类在简单题里，一拿到手上就想用个状态数组来标记0到mod-1的数字是否出现过，出现过就标记值为1，在一定次数后就判断这个数组值是否全为1，若全为1就是good choice。一开始纠结要操作多少次才能把这些数字全部计算出来，大致算了一下样例前两个，觉得次数在mod的基础上加一点就可以，所以就取了mod+10次。
提交的时候觉得这个方法有点太暴力，没想到过了，吃鲸！

然后要注意一下的就是严格控制输出格式，我是把数字转换为字符串来做，每组输出后是换行两次！

温习一下之前学到的字符串知识点。

（重要：数字->字符串）
    //创建stringstream流需要头文件，不同类型转换用法相同 
    int i;
    cin >> i;
    stringstream ss;
    ss << i;//将i输入ss流 
    ss >> s1;//ss流用string的格式输出给s1

最后放上代码

#include
using namespace std;
int vis[100005];
int main() {
  int step, mod, temp, flag, f;
  while(cin >> step >> mod) {
    temp = 0, flag = 0, f = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = 1;
    for (int i = 0; i < mod+10; i++) {
      temp = (temp+step)%mod; 
      vis[temp]= 1;
      if (i > mod) {
        for (int j = 0; j < mod; j++) {
          if (vis[j] == 0) {
            f = 1;
            break;

          }
        }
        if (!f) flag = 1; 
      }
    }
    stringstream ss1, ss2;
    string s1, s2;
    ss1 << step, ss2 << mod;
    ss1 >> s1, ss2 >> s2;
    for (int i = 0; i < 10-s1.length(); i++) cout << " ";
    cout << s1;
    for (int i = 0; i < 10-s2.length(); i++) cout << " ";
    cout << s2;
    cout << "    ";
    if (flag == 1) cout << "Good Choice" << endl <<endl;
    else cout << "Bad Choice" << endl <<endl;
  }
}

刚刚发现讨论区有更简单的方法，是自己太菜了，只要判断两个两个数字互质就行了，数论知识（TAT）gcd（step，mod） == 1

看大佬说原理是LCM（step，mod） （最小公倍数）== stepmod，LCM（step， mod） = stepmod/gcd(step, mod),
所以gcd（step，mod） == 1即可
但我还是不知道为什么是互质

#include
using namespace std;
int gcd(int a,int b) {
  return b == 0 ? a : gcd(b, a % b);
}
int main() {
  int a, b;
  while (cin >> a >> b) {
    printf("%10d%10d    ", a, b);
    printf(gcd(a, b) == 1 ? "Good Choice\n\n" : "Bad Choice\n\n");
  }
}