BZOJ2818: Gcd

题目描述

传送门

题目分析

题目就是在求：
\[ Ans=\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==prime] \]
直接算肯定不行，改成枚举质数
\[ Ans=\sum_{d\in prime}\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==d] \]
根据反演套路，设两个函数
\[ f(d)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d] \]
\[ F(n)=\sum_{n\mid d}f(d)=\lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor \]
根据莫比乌斯反演可以得到：
\[ f(n)=\sum_{n\mid d}\mu(\frac dn)F(d) \]
我们发现原式子后面的一坨就是\(f(d)\)

那么现在就是要求：

\[Ans=\sum_{d\in prime}f(d)\]
\[=\sum_{d\in prime}\sum_{d\mid p}\mu(\frac pd)F(p)\]
然后把枚举p换成枚举\(\frac pd\)
\[Ans=\sum_{d\in prime}\sum_{p=1}^{\frac nd}\mu(p)F(dp)\]
\[=\sum_{d\in prime}\sum_{p=1}^{\frac nd}\mu(p)(\lfloor \frac {n}{dp} \rfloor)^2\]
这个\(dp\)不是很方便我们把它替换成\(T\)

\[Ans=\sum_{T=1}^{n}\sum_{t|T,t\in prime}\mu(\lfloor\frac{T}{t}\rfloor)(\lfloor\frac{n}{T}\rfloor)^2\]
\((\lfloor\frac{n}{T}\rfloor)^2\)和\(t\)没关系，所以把它提出去
\[Ans=\sum_{T=1}^{n}(\lfloor\frac{n}{T}\rfloor)^2\sum_{t|T,t\in prime}\mu(\lfloor\frac{T}{t}\rfloor)\]
这样这个式子就可以在\(O(n)\)的复杂度内求出来了。

可以发现的是这个式子是可以进行整除分块的，所以如果有多组数据询问可以用整除分块将其优化成\(O(\sqrt n)\)的。

是代码呢

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e7+7;
#define ll long long
ll n,m,ans;
int g[MAXN],mu[MAXN],prime[MAXN];
bool vis[MAXN];
inline void get_mu(int N)
{
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            prime[++prime[0]]=i;mu[i]=-1;
        }
        for(int j=1;j<=prime[0];j++){
            if(prime[j]*i>N) break;
            vis[prime[j]*i]=1;
            if(i%prime[j]==0) break;
            else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int j=1;j<=prime[0];j++)
        for(int i=1;i*prime[j]<=N;i++) g[i*prime[j]]+=mu[i];
}
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    while(ch=='-')c*=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
int main()
{
    n=read();
    get_mu(n+1);
    for(int i=1;i<=n;i++) ans+=1ll*(n/i)*(n/i)*g[i];
    printf("%lld\n",ans);
}

BZOJ2818: Gcd

原文：https://www.cnblogs.com/victorique/p/10385552.html