【题解】CF1900D Small GCD 题解
PhainonK
·
·
题解
CF1900D Small GCD 题解
原题链接
题意
一个序列求所有三元组中两个较小的值的 \gcd 之和。
\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n}f(a_i,a_j,a_k)
## 思路
首先，朴素的做法就是直接按照给出的公式求解，时间复杂度大约为 $O(n^3\log n)$，显然是不行的，并且通常带有求和公式的题目都不会直接模拟计算。
由题可知三元组是不重复的（与三元组内元素出现的顺序无关），并且只需要用三元组中两个较小的值，从小到大排序是没有问题的。并且可以想到对于每一个三元组**枚举中间数**，对于中间数 $a_j$ 只需要将所有的 $i<j$ 的 $a_i$ 和 $a_j$ 求一个 $\gcd$ 即可，并且注意，因为三元组中的最大值是可以随意选取的，这个值需要乘一个 $(n-j)$。
如下：
$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)\times(n-i)
$$
时间复杂度顺利优化成 $O(n^2\log n)$。
但是这个时间复杂度还是远远不够的。但是还能怎么优化呢？
需要用到一个数论知识：
## 欧拉反演
**欧拉函数**：对正整数 $n$，欧拉函数是少于或等于 $n$ 的数中与 $n$ 互质的数的数目，用 $\phi(x)$来表示 $x$ 的欧拉函数值。
[欧拉函数如有不懂戳这里](http://oi-wiki.com/math/number-theory/euler-totient/)。
**欧拉反演**是欧拉函数的一条性质，即：
$$
n=\sum_{d|n}\phi(d)
$$
这里简单证明一下：
$$\begin{aligned}
n&=\sum_{d|n}\sum_{j=1}^{n}\gcd(j,n)==d \\
&=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}\gcd(j,\frac{n}{d})==1 \\
&=\sum_{d|n}\phi(\frac{n}{d}) \\
&=\sum_{d|n}\phi(d) \\
\end{aligned}$$
有了这条性质，可以应用：
一个较为简单的：
$$\begin{aligned}
\gcd(i,j)=\sum_{d|\gcd(i,j)}\phi(d)
=\sum_{d|i} \sum_{d|j} \phi(d)\\
\end{aligned}$$
所以：
$$\begin{aligned}
\sum_{i=1}^n\gcd(i,n)&=\sum_{i=1}^n\sum_{d|i} \sum_{d|n} \phi(d) \\
&=\sum_{d|n} \sum_{i=1}^n\sum_{d|i} \phi(d) \\
&=\sum_{d|n} \frac{n}{d}\phi(d)\\
\end{aligned}$$
将其应用到本题：
$$\begin{aligned}
&\sum_{i = 1}^{n} \sum_{j = 1}^{i - 1} \gcd(a_i, a_j) (n - i)\\
&= \sum_{i = 1}^{n} \sum_{j = 1}^{i - 1} \sum_{d | a_i, d | a_j} \phi(d)(n - i)\\
&= \sum_{i = 1}^{n} (n - i) \sum_{j = 1}^{i - 1} \sum_{d | a_i} \phi(d)[d | a_j] \\
&= \sum_{i = 1}^{n} (n - i) \sum_{d | a_i} \phi(d) \sum_{j = 1}^{i - 1} [d | a_j] \\
&= \sum_{i = 1}^{n} (n - i) \sum_{d | a_i} \phi(d) cnt_{i - 1, d}
\end{aligned}$$
对于欧拉函数，用一个欧拉筛就可以解决了。
最终时间复杂度：$O(n\sqrt{n})$。
## code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=8e4+10,Maxn=1e5+10;
int t,n,cnt=0;
ll a[N],prime[Maxn],phi[Maxn],sum[Maxn];
ll ans=0;
bool f[Maxn];
void phii(int x){//预处理欧拉函数
for(int i=2;i<=x;i++) f[i]=true;
f[1]=f[0]=false;
phi[1]=1;
for(int i=2;i<=x;i++){
if(f[i]) prime[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*prime[j]<=x;j++){
f[i*prime[j]]=false;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
return ;
}
int main(){
phii(1e5);
scanf("%d",&t);
while(t--){
memset(sum,0,sizeof(sum));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
for(int j=1;j*j<=a[i];j++){//枚举a[i]的所有因数
if(a[i]%j==0){
ans+=sum[j]*phi[j]*(n-i);
sum[j]++;//注意这里是先计算再修改
if(j*j!=a[i]){
ans+=sum[a[i]/j]*phi[a[i]/j]*(n-i);
sum[a[i]/j]++;
}
}
}
}
printf("%lld\n",ans);
ans=0;
}
return 0;
}
```
这个数学证明应该难度不算很高，读者有问题可以在评论区提出。看到了尽量回答。
完结撒花！