P3327约数个数和怎么为？
摘要：P3327 [SDOI2015] 约数个数和 大意 给定 (n, m)，求 (sum_{i=1}^n sum_{j=1}^m d(ij))，其中 (d(x)) 表示 (x) 的约数个数。 思路 [d(ij) = su
P3327 [SDOI2015] 约数个数和
大意
给定 \(n, m\)，求 \(\sum_{i=1}^n \sum_{j=1}^m d(ij)\)，其中 \(d(x)\) 表示 \(x\) 的约数个数。
思路
\[d(ij) = \sum_{x|i} \sum_{y|j} [\gcd(x, y) = 1]
\]
将该恒等式代入原式：
\[\text{Ans} = \sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} [\gcd(x, y) = 1]
\]
通过更换求和次序，先枚举 \(x\) 和 \(y\)。注意到在 \(1 \sim n\) 中，\(x\) 作为因子的次数为 \(\lfloor \frac{n}{x} \rfloor\)，同理 \(y\) 出现的次数为 \(\lfloor \frac{m}{y} \rfloor\)：
\[\text{Ans} = \sum_{x=1}^n \sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor [\gcd(x, y) = 1]
\]
利用莫比乌斯反演的性质 \([\gcd(x, y) = 1] = \sum_{k|\gcd(x, y)} \mu(k)\) 代入：
\[\text{Ans} = \sum_{x=1}^n \sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor \sum_{k|x, k|y} \mu(k)
\]
再次变换求和顺序，先枚举 \(k\)：
\[\text{Ans} = \sum_{k=1}^{\min(n, m)} \mu(k) \left( \sum_{x=1}^{\lfloor n/k \rfloor} \lfloor \frac{n}{kx} \rfloor \right) \left( \sum_{y=1}^{\lfloor m/k \rfloor} \lfloor \frac{m}{ky} \rfloor \right)
\]
令 \(S(N) = \sum_{i=1}^N \lfloor \frac{N}{i} \rfloor\)，则最终公式为：
\[\text{Ans} = \sum_{k=1}^{\min(n, m)} \mu(k) S(\lfloor \frac{n}{k} \rfloor) S(\lfloor \frac{m}{k} \rfloor)
\]
代码
#include<iostream>
using namespace std;
const int MAXN = 50005;
long long sum[MAXN];
int mu[MAXN], pr[MAXN], tot = 0;
long long S[MAXN], d[MAXN];
bool vis[MAXN];
void init(int n){
mu[1] = 1;
for(int i = 2;i <= n;i ++){
if(!vis[i]){
pr[++ tot] = i;
mu[i] = -1;
}
for(int j = 1;j <= tot && pr[j] * i <= n;j ++){
vis[pr[j] * i] = 1;
if(i % pr[j] == 0){
mu[i * pr[j]] = 0;
break;
}
mu[i * pr[j]] = -mu[i];
}
}
for(int i = 1;i <= n;i ++){
sum[i] = sum[i - 1] + mu[i];
}
for(int i = 1;i <= n;i ++){
for(int j = i;j <= n;j += i){
d[j] ++;
}
}
for(int i = 1;i <= n;i ++){
S[i] = S[i - 1] + d[i];
}
}
void solve(){
int n, m;
cin >> n >> m;
if(n > m) swap(n, m);
long long ans = 0;
for(int l = 1, r;l <= n;l = r + 1){
r = min(n / (n / l), m / (m / l));
ans += (long long)(sum[r] - sum[l - 1]) * S[n / l] * S[m / l];
}
cout << ans << '\n';
}
int main(){
init(MAXN - 4);
int t; cin >> t;
while(t --){
solve();
}
return 0;
}