传送门

以此题题解纪念我第一道独立思考出的数论题$QwQ$。

首先质数肯定是要筛的。

考虑对于某一个质数$p$，满足$gcd(i,j)=p$的$(i,j)$有多少对：

显然$p|i$且 $p|j$，则设$i=ap$，$j=bp$。

即$gcd(ap,bp)=p$

把$p$提出来：$gcd(a,b)*p=p$

约去$p$：$gcd(a,b)=1$，也就是$a$、$b$互质

假设$a>b$，问题就变成了求$a$所有取值的欧拉函数的和。$ap$不能超过$n$，则$1\le a\le \left\lfloor\dfrac{n}{p}\right\rfloor$。直接预处理出欧拉函数和前缀和。其中$a,b$可互换，答案乘$2$。当$a=1,b=1$时互换是同一种情况，答案减去$cnt$（$cnt$为质数个数）。

综上，$ans=\left(\sum\limits_{i=1}^{cnt}\sum\limits_{j=1}^{\left\lfloor\frac{n}{prime[i]}\right\rfloor}\varphi(j)\right)-cnt$

用的欧拉筛，时间复杂度$O(n)$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 10000005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
long long sum[maxn],ans;
int phi[maxn],prime[maxn>>2],cnt;
bool is[maxn];
int main(){
    int n=read();
    sum[1]=phi[1]=1;
    for(register int i=2;i<=n;++i){
        if(!is[i])prime[++cnt]=i,phi[i]=i-1;
        sum[i]=sum[i-1]+(long long)phi[i];
        for(register int j=1;j<=cnt&&prime[j]*i<=n;++j){
            is[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }    
    for(register int i=1;i<=cnt;++i)
        ans+=sum[n/prime[i]];
    printf("%lld\n",ans*2-(long long)cnt);
}