P2568 GCD

莫比乌斯反演基础入门题。

题目传送门

推式子：

$$\begin{aligned} \sum_{x}^{n}\sum_{y}^{n}[\gcd(x,y)=p],p\in prime &= \sum_{p}\sum_{x}^{\lfloor\frac{n}{p}\rfloor}\sum_{y}^{\lfloor\frac{n}{p}\rfloor}[\gcd(x,y)=1] \\&= \sum_{p}\sum_{x}^{\lfloor\frac{n}{p}\rfloor}\sum_{y}^{\lfloor\frac{n}{p}\rfloor}\sum_{d|\gcd(x,y)}\mu(d) \\&= \sum_{p}\sum_{d}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\sum_{x}^{\lfloor\frac{n}{pd}\rfloor}\sum_{y}^{\lfloor\frac{n}{pd}\rfloor} \\&= \sum_{p}\sum_{d}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\left\lfloor\frac{n}{pd}\right\rfloor^2 \\&= \sum_{T}^{n}\sum_{p|T}\mu(\frac{T}{p})\left\lfloor\frac{n}{pd}\right\rfloor^2,T=pd \end{aligned}$$

对于 $\displaystyle\sum_{p|T}\mu\left(\frac{T}{p}\right)$ ，我们可以在 $\mathcal O(n\ln n)$ 的时间内预处理，然后用 $\mathcal O(n)$ 的时间来枚举 $T$ 就可以计算答案了。

有几个我做题时卡壳的地方：

1. 这里的 $p$ 一定是质数，所以考虑代换 $d$ 而非 $p$ ；
2. 预处理时可以预处理到 $n$ ，也可以预处理到值域，但 $10^7$ 不要少看个零。
3. 记得开 long long 。

AC Code

#include<bits/stdc++.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=2e7+10;
int N,Tot;
ll Mu[MAXN],Mubi[MAXN],pri[MAXN];
bool is[MAXN];
inline void sieve(int n)
{
    Mu[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!is[i]) pri[++Tot]=i,Mu[i]=-1;
        for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
        {
            is[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            Mu[i*pri[j]]=-Mu[i];
        }
    }
    for(int i=1;i<=Tot;++i)
        for(int j=1;pri[i]*j<=n;++j)
            Mubi[j*pri[i]]+=Mu[j];
}
inline void solve(int n)
{
    ll res=0;
    for(int i=1;i<=n;++i) res+=1ll*Mubi[i]*(n/i)*(n/i);
    write(res);
}
int main()
{
    // freopen("gcd.in","r",stdin);
    // freopen("gcd.out","w",stdout);
    read(N);
    sieve(N);
    solve(N);
    return 0;
}
/*
4
*/