②拓展案例
拓展1：Σ gcd(i, n) —— 用 φ 求 gcd 之和
问题：给定 n（n ≤ 10⁷），求 Σ_{i=1}^{n} gcd(i, n)。
思路 按 gcd 分组
设 gcd(i, n) = d（d 必是 n 的约数）。则 gcd(i/d, n/d) = 1，且 1 ≤ i/d ≤ n/d。满足条件的 i/d 的个数恰好是 φ(n/d)。
所以 Σ_{i=1}^{n} gcd(i, n) = Σ_{d|n} d · φ(n/d)。
把 n 分解质因数后枚举所有约数 d，再逐个求 φ(n/d)，复杂度约 O(√n × √n)，比暴力 O(n log n) 快得多。
C++Σ gcd(i, n) — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll phi(ll n) {
ll res = n;
for (ll p = 2; p * p <= n; p++)
if (n % p == 0) { res = res / p * (p - 1); while (n % p == 0) n /= p; }
if (n > 1) res = res / n * (n - 1);
return res;
}
int main() {
ll n; cin >> n;
ll ans = 0;
for (ll d = 1; d * d <= n; d++) {
if (n % d) continue;
ans += d * phi(n / d); // 约数 d
if (d != n / d) ans += (n / d) * phi(d); // 配对约数 n/d
}
cout << ans << endl;
return 0;
}
运行结果
输入: 7
输出: 13
（gcd(1..7, 7) = 1,1,1,1,1,1,7，和为 13 ✓
公式：约数 d = 1, 7 → 1×φ(7) + 7×φ(1) = 6 + 7 = 13 ✓）
输入: 12
输出: 40
（手算：gcd(1..12, 12) = 1,2,3,4,1,6,1,4,3,2,1,12
和 = 1+2+3+4+1+6+1+4+3+2+1+12 = 40 ✓
公式：约数 d = 1, 2, 3, 4, 6, 12
d×φ(12/d) = 1×φ(12) + 2×φ(6) + 3×φ(4) + 4×φ(3) + 6×φ(2) + 12×φ(1)
= 1×4 + 2×2 + 3×2 + 4×2 + 6×1 + 12×1
= 4 + 4 + 6 + 8 + 6 + 12 = 40 ✓）
输入: 1000000007
输出: 1000000008
（素数 n 时 Σgcd = 1×φ(n) + n×φ(1) = (n-1) + n = 2n - 1 ✓）
💡 两个小坑
坑一：φ 的小表要背熟。φ(1)=1、φ(2)=1、φ(3)=2、φ(4)=2、φ(5)=4、φ(6)=2、φ(8)=4、φ(12)=4。上面 d = 3 那一项是 3×φ(4) = 3×2 = 6，而不是 3×1 —— 一旦记错，公式明明用对了也照样算不出正确答案。
坑二：配对约数别漏。枚举 d 从 1 到 √n，当 d ≠ n/d 时必须把 n/d 也计入一次，否则会漏掉大于 √n 的那些约数（例如 n = 12 时的 4、6、12）。
拓展2：RSA 加密的数学原理（欧拉定理的工业级应用）
问题：如何在不安全信道上传递消息，让窃听者拿到密文也无法还原？
RSA 的构造流程 欧拉定理
① 选两个大素数 p 与 q（各 1024 位以上），令 n = pq。
② 计算 φ(n) = (p−1)(q−1)，由积性得（因为 gcd(p, q) = 1）。
③ 选公钥指数 e：取一个与 φ(n) 互质的数（常用 65537）。
④ 求私钥指数 d：d = inv(e) mod φ(n)，即 e·d ≡ 1 (mod φ(n))。
⑤ 加密：c = m^e mod n（m 是明文数值）。解密：m = c^d mod n。
为什么解密能还原？因为 c^d = m^(e·d) = m^(1 + k·φ(n)) = m × (m^φ(n))^k ≡ m × 1^k = m (mod n) —— 中间这一步正是欧拉定理（要求 gcd(m, n) = 1）。
为什么安全？只知道 n 无法反推 p、q，因而算不出 φ(n)，也就求不出 d。大整数分解目前没有多项式算法。
C++RSA 玩具演示（小素数） — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) { x = 1; y = 0; return a; }
ll d = exgcd(b, a % b, y, x);
y -= a / b * x; return d;
}
ll qpow(ll base, ll exp, ll mod) {
ll res = 1 % mod; base %= mod;
while (exp) {
if (exp & 1) res = (__int128)res * base % mod;
base = (__int128)base * base % mod; exp >>= 1;
}
return res;
}
int main() {
ll p = 61, q = 53; // 演示用的小素数
ll n = p * q; // 3233
ll phiN = (p - 1) * (q - 1); // 3120
ll e = 17; // gcd(17, 3120) = 1
ll x, y; exgcd(e, phiN, x, y);
ll d = (x % phiN + phiN) % phiN; // d = inv(e) mod φ(n) = 2753
printf("n=%lld phi(n)=%lld 公钥e=%lld 私钥d=%lld\n", n, phiN, e, d);
ll msg = 65; // 明文（ASCII 的 'A'）
ll c = qpow(msg, e, n); // 加密
ll back = qpow(c, d, n); // 解密
printf("明文 %lld -> 密文 %lld -> 还原 %lld %s\n", msg, c, back, back == msg ? "OK" : "FAIL");
return 0;
}
运行结果
n=3233 phi(n)=3120 公钥e=17 私钥d=2753
明文 65 -> 密文 2790 -> 还原 65 OK
验算解密公式：
c^d = 2790^2753 mod 3233
由 e·d = 17 × 2753 = 46801 = 1 + 15 × 3120 = 1 + 15 × φ(n)
所以 m^(e·d) = m^(1 + 15·φ(n)) = m × (m^φ(n))^15 ≡ m × 1 = m (mod n) ✓
注意：真实 RSA 的 p、q 都有 1024 位以上，
n 约 617 位十进制，暴力分解完全不可行。
拓展3：可见点问题的二维推广
问题：求 Σ_{i=1}^{n} Σ_{j=1}^{n} [gcd(i, j) = 1]（有序互质对个数），n ≤ 10⁷。
方法一：直接用 φ 前缀和 O(n)
由前面的分析，有序互质对个数 = 2 Σ_{i=1}^{n} φ(i) − 1。欧拉筛打表后 O(1) 得到答案。
方法二：容斥 / 莫比乌斯反演 能扩展到更大 n
记 F(n) = Σ_{i,j≤n} [gcd(i,j) = 1]。用容斥（先数"gcd 是 d 的倍数"再逐层减）可以写成
F(n) = Σ_{d=1}^{n} μ(d) · ⌊n/d⌋²，其中 μ 是莫比乌斯函数。
当 n 达到 10¹¹ 时方法一失效（数组开不下），但方法二可以配合整除分块做到 O(√n) —— 这就是后续学习莫比乌斯反演的入口。
C++有序互质对计数 — 完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10000005;
int phi[MAXN], prime[MAXN], cnt;
bool vis[MAXN];
int main() {
int n; scanf("%d", &n);
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) { prime[++cnt] = i; phi[i] = i - 1; }
for (int j = 1; j <= cnt && (ll)i * prime[j] <= n; j++) {
int x = i * prime[j]; vis[x] = true;
if (i % prime[j] == 0) { phi[x] = phi[i] * prime[j]; break; }
phi[x] = phi[i] * (prime[j] - 1);
}
}
ll s = 0;
for (int i = 1; i <= n; i++) s += phi[i];
printf("%lld\n", 2 * s - 1); // 有序互质对个数
return 0;
}
运行结果
输入: 6
输出: 23
（Σφ(1..6) = 12，2×12 - 1 = 23 ✓
无序对 12 个，加上对称的 11 个（去掉重复的 (1,1)）得 23）
输入: 10
输出: 63
（Σφ(1..10) = 32，2×32 - 1 = 63 ✓ 与 C4 题的容斥结果一致）
输入: 10000000
输出: 60792708433043
（n = 10^7 时约 6.08×10^13，
6.08×10^13 / 10^14 ≈ 0.6079，与理论极限 6/π² ≈ 0.60793 吻合 ✓）