P3518 [POI2011] SEJ-Strongbox

Description

有一个密码箱，\(0\) 到 \(n-1\) 中的某些整数是它的密码。且满足：若 \(a\) 和 \(b\) 是它的密码，则 \((a+b)\bmod n\) 也是它的密码（\(a\)，\(b\) 可以相等）。某人试了 \(k\) 次密码，前 \(k-1\) 次都失败了，最后一次成功了。

问，该密码箱最多有多少种不同的密码。

Solution

若 \(x\) 为密码，那么 \(2x \bmod n, 3x \bmod n,...\) 都会是密码。

我们有引理：

Lemma 1

若 \(x\) 为密码，那么 \(\gcd(x,n)\) 也必定是密码。

列出同余方程 \(kx \equiv\gcd(x,n) \pmod{n}\)，化为 \(kx+pn=\gcd(x,n)\)，方程必定有解。

Lemma 2

若 \(x,y\) 为密码，那么 \(\gcd(x,y)\) 也必定是密码。

首先关于 \(p,q\) 的方程 \(px+qy=\gcd(x,y)\) 一定有整数解。

在模 \(n\) 意义下，将 \(p,q\) 通过加若干次 \(n\) 变为非负整数，同余号依然成立。

则 \(p,q\) 一定可以全部取到非负整数。

Lemma 3

设最小的密码为 \(x\)，其余密码一定是 \(x\) 的若干正整数倍。

反证法。假设最小的密码是 \(x\)，存在一个密码 \(y\) 不是 \(x\) 的倍数。