P2568 GCD是什么意思？
摘要：P2568 GCD 大意 求 (gcd(x, y) = p) 的个数。 思路 [text{Ans} = sum_{p le n} sum_{i=1}^{lfloor np rfloor} sum_{j=1}^{lf
P2568 GCD
大意
求 \(\gcd(x, y) = p\) 的个数。
思路
\[\text{Ans} = \sum_{p \le n} \sum_{i=1}^{\lfloor n/p \rfloor} \sum_{j=1}^{\lfloor n/p \rfloor} [\gcd(i, j) = 1]
\]
\[\text{Ans} = \sum_{p \le n} \sum_{d=1}^{\lfloor n/p \rfloor} \mu(d) \lfloor \frac{n}{pd} \rfloor^2
\]
令 \(T = pd\)，通过更换求和次序：
\[\text{Ans} = \sum_{T=1}^n \lfloor \frac{n}{T} \rfloor^2 \left( \sum_{p|T, p \in \text{prime}} \mu(\frac{T}{p}) \right)
\]
代码
#include<iostream>
using namespace std;
const int MAXN = 1e7 + 5;
bool vis[MAXN];
int mu[MAXN], f[MAXN];
int pr[MAXN], tot;
long long sum[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;pr[j] * i <= n && j <= tot;j ++){
vis[pr[j] * i] = 1;
if(i % pr[j] == 0){
mu[pr[j] * i] = 0;
break;
}
mu[pr[j] * i] = -mu[i];
}
}
for(int j = 1;j <= tot;j ++){
for(int i = 1;i * pr[j] <= n;i ++){
f[i * pr[j]] += mu[i];
}
}
for(int i = 1;i <= n;i ++){
sum[i] = sum[i - 1] + f[i];
}
}
void solve(){
int n, m; cin >> n; m = n;
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)(n / l) * (m / l) * (sum[r] - sum[l - 1]);
}
cout << ans << '\n';
}
int main(){
init(MAXN - 5);
// int t; cin >> t;
// while(t --){
solve();
// }
return 0;
}