题解 P1390 【公约数的和】
i9_7980XE
2018-06-16 22:28:31
## 背景
无意中看到小伙伴$@OYSJ$在写这道题，看了下题目，印象中可以用莫比乌斯水过，发现真的可以用诶，开心qwq。
关于莫比乌斯反演[点我点我](http://www.cinema000.xyz/1082.ruby)
三倍经验：[UVa11417](https://www.luogu.org/problemnew/show/UVA11417)，[UVa11426](https://www.luogu.org/problemnew/show/UVA11426)
## 分析
本题就是求
$$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\gcd(i,j)$$
然后我们可以先求有重复元素的，然后减去重复的好了，这样方便套反演。
枚举最大公约数$d$然后转化成可以分块的形式（准确的说应该是分块思想，公共乘积优化），
$$\begin{aligned}\sum_{i = 1}^n\sum_{j = 1}^m\gcd(i, j)& = \sum_{d = 1}^nd\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i, j) = d]\\& = \sum_{d = 1}^nd\sum_{x=1}^{\left\lfloor\frac n d\right\rfloor}\mu(x)\left\lfloor\frac n {dx}\right\rfloor\left\lfloor\frac m {dx}\right\rfloor\end{aligned}$$
套分块$O((\sqrt(n)^2)=O(n)$，当然计算过程中溢出了，懒得优化什么的了，直接上了$int128$，应用$double$或高精吧。
```cpp
#include<cstdio>
#include<algorithm>
using std::fill;using std::swap;
typedef unsigned long long int64;
const int MAXN = 2000000 + 6;
int primes[MAXN],mu[MAXN],num,sum[MAXN];
bool isPrime[MAXN];
inline int min(int a,int b){return a < b ? a : b;}
void sieve(){
fill(isPrime,isPrime + MAXN,true);
num = 0;mu[1] = 1;
for(int i = 2;i < MAXN;++i){
if(isPrime[i]) primes[num++] = i,mu[i] = -1;
static int d;
for(int j = 0;j < num && (d = i * primes[j]) < MAXN;++j){
isPrime[d] = false;
if(i % primes[j] == 0){
mu[d] = 0;break;
}else mu[d] = -mu[i];
}
}
sum[0] = 0;
for(int i = 1;i < MAXN;i++) sum[i] = sum[i - 1] + mu[i];
}
int64 f(int n,int m,int d){
if(n > m) swap(n,m);
int64 ans = 0;
n /= d,m /= d;
for(int i = 1,last = 1;i <= n;i = last + 1){
last = min(n / (n / i),m / (m / i));
ans += (__int128)((sum[last] - sum[i - 1]) * (__int128)(n / i) * (m / i));
}
return ans;
}
int main(){
sieve();
int64 n;scanf("%llu",&n);
int64 ans = 0;
for(int d = 1;d <= n;d++){
ans += d * f(n,n,d);
}
printf("%llu",(ans - n * (n + 1) / 2) / 2);
return 0;
}
```