当前位置：首页 > news >正文

UVa 408 Uniform Generator

news 2026/6/13 12:15:25

题目描述

题目涉及一种伪随机数生成器，其递推公式为：

seed(x+1)=[seed(x)+STEP]%MOD \textit{seed}(x + 1) = [\textit{seed}(x) + \textit{STEP}] \% \textit{MOD}seed(x+1)=[seed(x)+STEP]%MOD

其中%\%%为取模运算符。该生成器会产生000到MOD−1\textit{MOD} - 1MOD−1之间的伪随机数序列。如果STEP\textit{STEP}STEP和MOD\textit{MOD}MOD选择得当，该序列可以在MOD\textit{MOD}MOD次迭代内生成000到MOD−1\textit{MOD} - 1MOD−1之间的所有整数，从而实现均匀分布。

例如，STEP=3\textit{STEP} = 3STEP=3，MOD=5\textit{MOD} = 5MOD=5时，序列为0,3,1,4,20, 3, 1, 4, 20,3,1,4,2，覆盖了000到444的所有数字。而STEP=15\textit{STEP} = 15STEP=15，MOD=20\textit{MOD} = 20MOD=20时，序列为0,15,10,5,…0, 15, 10, 5, \ldots0,15,10,5,…，无法覆盖所有数字。

本题要求判断给定的STEP\textit{STEP}STEP和MOD\textit{MOD}MOD是否能生成均匀分布的伪随机数序列。

输入格式

输入包含多行，每行两个整数STEP\textit{STEP}STEP和MOD\textit{MOD}MOD（1≤STEP,MOD≤1000001 \le \textit{STEP}, \textit{MOD} \le 1000001≤STEP,MOD≤100000）。

输出格式

对于每行输入，输出三部分：

STEP\textit{STEP}STEP值，右对齐占第111到101010列。
MOD\textit{MOD}MOD值，右对齐占第111111到202020列。
从第252525列开始，左对齐输出Good Choice\texttt{Good Choice}Good Choice或Bad Choice\texttt{Bad Choice}Bad Choice。

每组输出后跟一个空行。

样例

输入

3 5 15 20 63923 99999

输出

3 5 Good Choice 15 20 Bad Choice 63923 99999 Good Choice

题目分析

本题的核心是判断线性同余生成器xn+1=(xn+STEP) mod MODx_{n+1} = (x_n + \textit{STEP}) \bmod \textit{MOD}xn+1=(xn+STEP)modMOD是否具有最大周期MOD\textit{MOD}MOD，即能否在MOD\textit{MOD}MOD次迭代内生成000到MOD−1\textit{MOD} - 1MOD−1的所有整数。

周期条件

从初始值000开始，序列为：
0, STEP mod MOD, 2×STEP mod MOD, 3×STEP mod MOD, … 0,\ \textit{STEP} \bmod \textit{MOD},\ 2 \times \textit{STEP} \bmod \textit{MOD},\ 3 \times \textit{STEP} \bmod \textit{MOD},\ \ldots0,STEPmodMOD,2×STEPmodMOD,3×STEPmodMOD,…

一般项为k×STEP mod MODk \times \textit{STEP} \bmod \textit{MOD}k×STEPmodMOD。该序列的周期等于满足k×STEP≡0(modMOD)k \times \textit{STEP} \equiv 0 \pmod{\textit{MOD}}k×STEP≡0(modMOD)的最小正整数kkk，即MOD/gcd⁡(STEP,MOD)\textit{MOD} / \gcd(\textit{STEP}, \textit{MOD})MOD/gcd(STEP,MOD)。

因此，序列能生成所有MOD\textit{MOD}MOD个不同余数的充要条件是：
MODgcd⁡(STEP,MOD)=MOD⟺gcd⁡(STEP,MOD)=1 \frac{\textit{MOD}}{\gcd(\textit{STEP}, \textit{MOD})} = \textit{MOD} \quad \Longleftrightarrow \quad \gcd(\textit{STEP}, \textit{MOD}) = 1gcd(STEP,MOD)MOD=MOD⟺gcd(STEP,MOD)=1

也就是说，STEP\textit{STEP}STEP与MOD\textit{MOD}MOD互质时，生成器是均匀的；否则不是。

数学解释

线性同余生成器xn+1=(xn+a) mod mx_{n+1} = (x_n + a) \bmod mxn+1=(xn+a)modm的周期等于m/gcd⁡(a,m)m / \gcd(a, m)m/gcd(a,m)。这是因为每次增加aaa，相当于在模mmm的加法群中移动。群中由aaa生成的子群的大小为m/gcd⁡(a,m)m / \gcd(a, m)m/gcd(a,m)。只有当gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1时，该子群才是整个群，周期达到最大值mmm。

算法实现

对于每组STEP\textit{STEP}STEP和MOD\textit{MOD}MOD，使用欧几里得算法计算最大公约数：

若gcd⁡(STEP,MOD)=1\gcd(\textit{STEP}, \textit{MOD}) = 1gcd(STEP,MOD)=1，输出Good Choice\texttt{Good Choice}Good Choice。
否则，输出Bad Choice\texttt{Bad Choice}Bad Choice。

注意输出格式：STEP\textit{STEP}STEP和MOD\textit{MOD}MOD各占101010列宽度，右对齐；然后输出444个空格；最后输出判断结果。每组输出后需打印一个空行。

复杂度分析

每组数据使用欧几里得算法求最大公约数，时间复杂度O(log⁡min⁡(STEP,MOD))O(\log \min(\textit{STEP}, \textit{MOD}))O(logmin(STEP,MOD))，完全可接受。

代码实现

// Uniform Generator// UVa ID: 408// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intSTEP,MOD;while(cin>>STEP>>MOD){cout<<setw(10)<<right<<STEP;cout<<setw(10)<<right<<MOD;cout<<string(4,' ');inttemp,a=STEP,b=MOD;while(a%b)temp=a,a=b,b=temp%b;if(b==1)cout<<"Good Choice\n\n";elsecout<<"Bad Choice\n\n";}return0;}