const int MAXN = 1e7; // 根据题目需求调整最大值 int mu[MAXN + 1]; bool is_prime[MAXN + 1]; vector; void init_mobius() { memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; mu[1] = 1; // 初始化n=1的情况 for (int i = 2; i N; ++i) { if (is_prime[i]) { // i是质数 prime.push_back(i); mu[i] = -1; // 单个质数，m=1，mu=-1 } for (int p : prime) { if (i * p > MAXN) break; is_prime[i * p] = false; if (i % p == 0) { // p是i的因子，i*p有平方因子 mu[i * p] = 0; break; } else { // p与i互质，积性函数性质 mu[i * p] = mu[i] * mu[p]; } } } }int solve(int a, int b, int d) { a /= d; b /= d; if (a > b) swap(a, b); int res = 0; for (int l = 1, r; l l = r + 1) { r = min(a / (a / l), b / (b / l)); // 整除分块 res += (prefix_mu[r] - prefix_mu[l - 1]) * (a / l) * (b / l); } return res; }#include h> using namespace std; const int MAXN = 5e4; // 题目数据范围通常为1e4~1e5，5e4足够覆盖 int mu[MAXN + 1]; bool is_prime[MAXN + 1]; vector<int> prime; long long prefix_mu[MAXN + 1]; // 前缀和（用long long避免溢出） // 初始化莫比乌斯函数和前缀和 void init_mobius() { memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; mu[1] = 1; for (int i = 2; i N; ++i) { if (is_prime[i]) { prime.push_back(i); mu[i] = -1; } for (int p : prime) { if (i * p > MAXN) break; is_prime[i * p] = false; if (i % p == 0) { mu[i * p] = 0; break; } else { mu[i * p] = mu[i] * mu[p]; } } } // 预处理前缀和 prefix_mu[0] = 0; for (int i = 1; i ) { prefix_mu[i] = prefix_mu[i - 1] + mu[i]; } } // 计算 1<=xX, 1<=Y 且 gcd(x,y)=k 的数对个数 long long calc(int X, int Y, int k) { if (X == 0 || Y == 0) return 0; X /= k; Y /= k; if (X > Y) swap(X, Y); long long res = 0; // 整除分块优化求和 for (int l = 1, r; l + 1) { r = min(X / (X / l), Y / (Y / l)); res += (prefix_mu[r] - prefix_mu[l - 1]) * 1LL * (X / l) * (Y / l); } return res; } int main() { init_mobius(); int T; cin >> T; while (T--) { int a, b, c, d, k; cin >> a >> b >> c >> d >> k; long long ans = calc(b, d, k) - calc(a - 1, d, k) - calc(b, c - 1, k) + calc(a - 1, c - 1, k); cout < < return 0; }const int MOD = 20101009; const int MAXN = 1e7; int mu[MAXN + 1]; bool is_prime[MAXN + 1]; vector long long pre_sum[MAXN + 1]; // pre_sum[k] = sum_{i=1}^k mu[i] * i^2 mod MOD // 预处理莫比乌斯函数和 pre_sum void init() { memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; mu[1] = 1; for (int i = 2; i i) { if (is_prime[i]) { prime.push_back(i); mu[i] = -1; } for (int p : prime) { if (i * p > MAXN) break; is_prime[i * p] = false; if (i % p == 0) { mu[i * p] = 0; break; } else { mu[i * p] = mu[i] * mu[p]; } } } // 计算 pre_sum：mu[k] * k^2 mod MOD for (int k = 1; k k) { long long k2 = 1LL * k * k % MOD; pre_sum[k] = (pre_sum[k - 1] + 1LL * mu[k] * k2) % MOD; } // 处理负号（确保结果非负） for (int k = 1; k MAXN; ++k) { if (pre_sum[k] ) pre_sum[k] += MOD; } } // 计算 sum(1~n) mod MOD long long sum(long long n) { n %= MOD; return n * (n + 1) / 2 % MOD; } // 计算 S(A,B) long long compute_S(int A, int B) { if (A == 0 || B == 0) return 0; if (A > B) swap(A, B); long long res = 0; for (int l = 1, r; l r + 1) { r = min(A / (A / l), B / (B / l)); long long s = (pre_sum[r] - pre_sum[l - 1] + MOD) % MOD; long long sa = sum(A / l); long long sb = sum(B / l); res = (res + s * sa % MOD * sb % MOD) % MOD; } return res; } // 计算最终答案 long long solve(int n, int m) { if (n > m) swap(n, m); long long ans = 0; for (int l = 1, r; l ; l = r + 1) { r = min(n / (n / l), m / (m / l)); long long d_sum = (1LL * (l + r) * (r - l + 1) / 2) % MOD; // 求和 d from l to r long long s = compute_S(n / l, m / l); ans = (ans + d_sum * s % MOD) % MOD; } return ans; }// 计算 sum_{d=1}^n f(d) * g( floor(n/d) ) long long divide_block(int n, function f, function(int)> g) { long long res = 0; for (int l = 1, r; l l = r + 1) { r = n / (n / l); long long f_sum = 0; for (int i = l; i ++i) f_sum += f(i); // 可预处理前缀和优化 res += f_sum * g(n / l); } return res; }6.3 寄语
莫比乌斯反演的核心是 “转化与优化”—— 将难以直接计算的问题转化为可通过数论性质快速求解的形式。初学者可能会被公式推导和代码实现劝退，但只要循序渐进（先掌握基础例题，再挑战进阶题），多动手推导公式、调试代码，就能逐渐体会其魅力。
算法竞赛中，莫比乌斯反演常与整除分块、前缀和、线性筛结合出现，建议将这些知识点串联学习，形成完整的数论解题体系。祝你在数论的世界里越走越远！
