BZOJ 2820: YY的GCD 莫比乌斯反演_数学推导

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$

按套路前提 $gcd(i,j)$

$\Rightarrow\sum_{d=1}^{n}d\in prime\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==d]$

后面的 $\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==d]$ 是反演模板

$\Rightarrow \sum_{b=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\mu(b)\left \lfloor \frac{n}{db} \right \rfloor \left \lfloor \frac{m}{db} \right \rfloor$

答案为 $\sum_{d=1}^{n}d\in prime \sum_{b=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\mu(b)\left \lfloor \frac{n}{db} \right \rfloor \left \lfloor \frac{m}{db} \right \rfloor$

用这个式子整除分块算是 $O(n)$ 的，我们优化一下.

令 $T=db$

则原式 $=\sum_{T=1}^{n}\left \lfloor \frac{n}{T} \right \rfloor\left \lfloor \frac{m}{T} \right \rfloor\sum_{d|T,d\in prime}\mu(\frac{T}{d})$

发现后面的 $\sum_{d|T,d\in prime}\mu(\frac{T}{d})$ 可以提前预处理（只需枚举质数并暴力更新就行）

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#define maxn 10000009

const long long N = 10000009 ;

#define ll long long

#define setIO(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

using namespace std;

int vis[maxn],prime[maxn],mu[maxn],g[maxn],tot;

long long sumv[maxn];

void init(){

    mu[1]=1;

    for(int i=2;i<maxn;++i) {

        if(!vis[i]) { prime[++tot]=i,mu[i]=-1; }

        for(int j=1;j<=tot && (ll)prime[j]*i < (ll)maxn;++j)

        {

            vis[prime[j]*i]=1;

            if(i % prime[j]==0) {

                mu[i * prime[j]]=0;

                break;

            }

            mu[i * prime[j]]=-mu[i];

        }

    }

    for(int i=1;i<=tot;++i)

        for(ll j=1;(ll)j*prime[i]<N;++j)

            g[prime[i]*j]+=mu[j];

    for(int i=1;i<=10000000;++i) sumv[i] = (long long)sumv[i-1]+g[i];

}

ll work(int n,int m) {

    if(n>m) swap(n,m);

    long long ans=0;

    for(ll i=1,j;i<=n;i=j+1) {

        j = min(n/(n/i),m/(m/i));

        ans += (n/i) * (m/i) * (sumv[j] - sumv[i-1]);

    }

    return ans;

}

int main(){

    //setIO("input");

    init();

    int T,x,y; scanf("%d",&T);

    while(T--) scanf("%d%d",&x,&y),printf("%lld\n",work(x,y));

    return 0;

}

巴特西

BZOJ 2820: YY的GCD 莫比乌斯反演_数学推导_线性筛

最新文章

热门文章