[51Nod 1584] 加权约数和（约数和函数性质 + 莫比乌斯反演） | 错题本
文章目录
- 题目
- 分析
- 代码
题目
分析
先把 \max\{i, j\} 去掉：
原式=2\sum_{i = 1}^{N}\sum_{j = 1}^i i\sigma(ij)-\sum_{i = 1}^N i\sigma(i^2)
推式子前先介绍约数和函数有一个重要性质（和约数个数一样可以转化为 \gcd 问题）：\begin{aligned}\sigma(xy)=&\sum_{i|x}\sum_{j|y}ij\left[\gcd\left(i, \frac{y}{j}\right)=1\right]\\ =&\sum_{i| x}\sum_{j|y}i\frac{y}{j}[\gcd(i, j) = 1]\end{aligned} 证明时考虑我们从 x 中枚举一个因数 i，从 y 中枚举一个因数 j，为了确保不算重，我们规定同一个质因子先从 y 中取到 j 里面，取完了再从 x 中取到 i 里面，这样的话所有 ij 都是 xy 的因数且不会算重。如何保证每个质因子都是先从 y 中取的呢？只需要看 \frac{y}{j} 中的某个质因数在不在 i 中，如果在，就意味着 y 中的这个质因数还没有取完，我们就从 x 中取了，这是不合法的，于是第一个等号得证，第二个等号就显然了。
首先计算第一个部分并将上述公式代入后得到以下结果：\begin{aligned}&\sum_{i = 1}^{N}\sum_{j = 1}^i i\sigma(ij)\\ =&\sum_{i = 1}^{N}\sum_{j = 1}^i i\sum_{x|i}\sum_{y|j}x\frac{j}{y}[\gcd(x, y) = 1]\end{aligned} 进行反演后上式变为：$$\begin{aligned}&\sum_{i = 1}^{N}\sum_{j = 1}^i i\sum_{x|i}\sum_{y|j}x\frac{j}{y}\sum_{d|\gcd(x, y)} \mu(d)\ =&\sum_{d = 1}^N\mu(d)\sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{i}di \cdot \frac{j}{y}\ =&\sum_{d = 1}^N\mu(d)\sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{i}\frac{di \cdot j}{y}\ =&~…（后续内容略）
对于任何满足形式
A(N)= \sum _{i=1}^{N} f(i)\cdot \sum _{j=1}^{\left \lfloor \dfrac {N}{i}\right \rfloor }g(j)
的表达式，在已知函数f,g的情况下都可以在时间复杂度上达到O(N log N)，从而预处理所有的值序列$. 这一结论来源于其递推关系式：
A(N)= A(N-1)+ (f*g)(N)
可以看出当计算到第N项时，
A[N] = A[N-1] + \sum _{d|n} f(d)\cdot g(n/d)
即等于当前增量带来的额外变化量与之相关. 进而可以通过调和级数的方法来计算所有的卷积结果.
针对这道题的求解过程，在解决此问题时，首先进行μ和σ的线性筛选，在完成上述操作后进行相应的优化计算流程
代码
#include <bits/stdc++.h>
int Read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
x = x * 10 + (c ^ 48), c = getchar();
return x;
}
typedef long long LL;
const int MAXN = 1000000;
const int MOD = 1000000007;
inline int Add(int x, const int &y) {
return ((x += y) >= MOD) ? (x - MOD) : x;
}
inline int Mul(const int &x, const int &y) {
return (LL)x * y % MOD;
}
inline int Sub(int x, const int &y) {
return ((x -= y) < 0) ? (x + MOD) : x;
}
int Mu[MAXN + 5];
LL Sig[MAXN + 5], Low[MAXN + 5];
bool Vis[MAXN + 5];
std::vector<int> Pri;
int Ans[MAXN + 5], S[MAXN + 5];
void Init(int n) {
Mu[1] = Sig[1] = Low[1] = S[1] = 1;
for (int i = 2; i <= n; i++) {
if (!Vis[i])
Mu[i] = MOD - 1, Sig[i] = Low[i] = 1 + i, Pri.push_back(i);
for (int j = 0, k; j < (int)Pri.size() && i * Pri[j] <= n; j++) {
Vis[k = i * Pri[j]] = true;
if (i % Pri[j] == 0) {
Mu[k] = 0;
Low[k] = 1 + Low[i] * Pri[j];
Sig[k] = Sig[i] / Low[i] * Low[k];
break;
}
Mu[k] = MOD - Mu[i];
Low[k] = 1 + Pri[j];
Sig[k] = Sig[i] * Low[k];
}
S[i] = Add(S[i - 1], Sig[i] % MOD);
}
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i)
Ans[j] = Add(Ans[j], Mul(Mu[i], Mul(i, Mul(i, Mul(j / i, Mul(Sig[j / i], Sub(Mul(2, S[j / i]), Sig[j / i])))))));
for (int i = 1; i <= n; i++)
Ans[i] = Add(Ans[i], Ans[i - 1]);
}
int main() {
Init(MAXN);
int T = Read(), Cas = 0;
while (T--)
printf("Case #%d: %d\n", ++Cas, Ans[Read()]);
return 0;
}
代码解释