NOI数学算法实战BSGS与狄利克雷卷积的高效实现与竞赛应用在信息学竞赛的数学板块中大步小步算法(BSGS)和狄利克雷卷积是两个既基础又关键的高频考点。本文将深入探讨这两种算法的核心原理、竞赛中的典型应用场景并提供可直接用于NOI/CSP赛事的优化C实现模板。不同于纯理论讲解我们更关注算法在时间/空间复杂度上的实际表现以及如何根据题目特点进行灵活调整。1. 大步小步算法(BSGS)的原理与实现离散对数问题是许多密码学系统和竞赛题目的数学基础给定质数p、生成元g和整数y求解满足g^x ≡ y (mod p)的最小非负整数x。BSGS算法正是解决这类问题的标准工具其时间复杂度为O(√p)相比暴力搜索的O(p)有显著提升。1.1 算法核心思想BSGS算法将问题分解为大步和小步两部分小步预计算g^0, g^1, ..., g^(m-1) mod p并存入哈希表m通常取⌈√p⌉大步枚举j检查y*(g^(-m))^j是否存在于哈希表中当两者匹配时得到x j*m i的解。这种时间-空间折衷的策略是典型的平方根算法设计范式。#include unordered_map #include cmath // 快速幂算法 (用于计算逆元) long long qpow(long long a, long long b, long long p) { long long res 1; while (b) { if (b 1) res res * a % p; a a * a % p; b 1; } return res; } // BSGS算法实现 long long bsgs(long long g, long long y, long long p) { g % p, y % p; if (y 1 || p 1) return 0; if (g 0) return y 0 ? 1 : -1; long long m ceil(sqrt(p)); std::unordered_maplong long, long long table; // 小步构建哈希表 long long curr 1; for (long long i 0; i m; i) { if (!table.count(curr)) table[curr] i; curr curr * g % p; } // 大步寻找碰撞 long long gm qpow(g, p - 1 - m, p); // g^(-m) curr y; for (long long j 0; j m; j) { if (table.count(curr)) { long long x j * m table[curr]; if (x 0) return x; } curr curr * gm % p; } return -1; // 无解 }1.2 复杂度分析与优化技巧BSGS的标准实现具有以下性能特征操作时间复杂度空间复杂度预计算阶段O(√p)O(√p)查询阶段O(√p)O(1)整体O(√p)O(√p)竞赛中的实用优化哈希表选择unordered_map平均O(1)但可能有较大常数数据规模小时可用数组替代块大小调整当p较小时可直接使用p而非⌈√p⌉提前终止找到第一个可行解即可返回不必遍历所有可能性注意当p不是质数时需要先处理g与p不互质的情况这涉及到更复杂的扩展BSGS算法。在竞赛中题目通常会保证p为质数以简化问题。2. 狄利克雷卷积的理论与高效计算狄利克雷卷积是数论函数之间的重要运算定义为 (f∗g)(n) Σ_{d|n} f(d)g(n/d)这种运算在莫比乌斯反演、筛法优化等问题中频繁出现理解其性质对解决NOI级别的数论题目至关重要。2.1 常见数论函数及其卷积函数名称定义卷积性质单位函数ε(n) [n 1]f∗ε f恒等函数id(n) nμ∗id φ莫比乌斯函数μ(n)μ∗1 ε欧拉函数φ(n)φ∗1 id约数个数函数d(n) Σ_{dn} 12.2 线性筛法实现卷积对于积性函数可以在O(n)时间内预处理出函数值const int MAXN 1e6 5; int phi[MAXN], mu[MAXN], d[MAXN]; bool is_prime[MAXN]; vectorint primes; void sieve() { fill(is_prime, is_prime MAXN, true); phi[1] mu[1] d[1] 1; for (int i 2; i MAXN; i) { if (is_prime[i]) { primes.push_back(i); phi[i] i - 1; mu[i] -1; d[i] 2; } for (int p : primes) { if (i * p MAXN) break; is_prime[i * p] false; if (i % p 0) { phi[i * p] phi[i] * p; mu[i * p] 0; int cnt 1, tmp i; while (tmp % p 0) tmp / p, cnt; d[i * p] d[i] / cnt * (cnt 1); break; } else { phi[i * p] phi[i] * phi[p]; mu[i * p] mu[i] * mu[p]; d[i * p] d[i] * d[p]; } } } }2.3 卷积的快速计算当需要计算特定(f∗g)(n)时可以采用分块优化技术// 计算(f∗g)(n) Σ_{i1}^n f(i)g(⌊n/i⌋) long long dirichlet_conv(int n, const vectorlong long f, const vectorlong long g) { long long res 0; for (int l 1, r; l n; l r 1) { r n / (n / l); res (f[r] - f[l-1]) * g[n / l]; } return res; }这种方法的时间复杂度为O(√n)非常适合处理n高达1e12的大规模数据。3. 竞赛中的综合应用案例3.1 BSGS解离散对数问题例题给定p998244353, g3, y123456789求最小x使g^x ≡ y mod p。void solve_bsgs_example() { long long p 998244353, g 3, y 123456789; long long x bsgs(g, y, p); if (x -1) { cout No solution exists endl; } else { // 验证解的正确性 long long check 1; for (int i 0; i x; i) check check * g % p; cout Solution x x , verification: check endl; } }3.2 狄利克雷卷积优化数论求和例题计算Σ_{i1}^n Σ_{j1}^m gcd(i,j) for n,m ≤ 1e6。利用φ∗1id的性质可将问题转化为 Σ_{d1}^min(n,m) φ(d)⌊n/d⌋⌊m/d⌋long long gcd_sum(int n, int m) { sieve(); // 预处理φ数组 if (n m) swap(n, m); long long res 0; for (int d 1; d n; d) { res phi[d] * (n / d) * (m / d); } return res; }4. 性能对比与算法选择在实际竞赛中根据数据规模选择合适算法至关重要算法适用场景时间复杂度空间复杂度BSGS标准版p ≤ 1e16O(√p)O(√p)BSGS哈希优化版p ≤ 1e18 (但√p可存储)O(√p)O(√p)线性筛预处理n ≤ 1e7O(n)O(n)分块计算n ≤ 1e12O(√n)O(1)调试技巧对于BSGS总是验证找到的解是否确实满足原方程对于狄利克雷卷积检查边界条件如n1使用小数据手工计算验证算法正确性