P2568

· · 个人记录

GCD

推导还是相当有意思的。

Ans=\sum_{p\le n}\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=p]

然后，

\begin{aligned}Ans&=\sum_{p\le n}\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{p}\rfloor}[\gcd(i,j)=1]\\&=\sum_{p\le n}(2\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{i}[\gcd(i,j)=1]-1)\end{aligned}

不过是改变了一下枚举方式，最后把重复统计的 i=j=1 去掉。

由 \sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}(\sum_{j=1}^{i}[\gcd(i,j)=1])=\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\varphi(i) ，可知，

Ans=\sum_{p\le n}(2\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\varphi(i)-1)

然后用一下前缀和，就可以 O(n) 求了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e7,M=7e5;

ll n,ans,cnt;

bool f[N+5];

ll prime[M+5],phi[N+5],c[N+5];

void init() {
    f[1]=0;phi[1]=1;c[1]=1;
    for(ll i=2;i<=n;i++) {
        if(!f[i]) {prime[++cnt]=i;phi[i]=i-1;}
        for(ll j=1;j<=cnt&&i*prime[j]<=n;j++) {
            f[i*prime[j]]=1;
            if(i%prime[j]) {
                phi[i*prime[j]]=(prime[j]-1)*phi[i];
            }
            else {
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
        }
        c[i]=c[i-1]+phi[i];
    }
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    init();

    for(ll i=1;i<=cnt;i++) {
        if(prime[i]>n) break;
        ans+=2*c[n/prime[i]]-1;
    }

    write(ans);

    return 0;
}