首页 > 代码库 > BZOJ2820 YY的GCD 莫比乌斯反演

BZOJ2820 YY的GCD 莫比乌斯反演

2024-09-06 05:01:49   210人阅读

题意：求x∈[1,N],y∈[1,M]中gcd(x,y)为质数的数对的数量。

题解：

这个题把BZOJ2301中的k改成枚举素数就能过啦……才怪，不过和那个题的思路类似，但我们不枚举每一个质数，而是直接枚举质数p的倍数T，得到\[{f_{A,B,p}} = \sum\limits_{p|T} {[{F_{A,B,T}}\sum\limits_{p|T} {\mu (\frac{T}{p})} ]} \]其中F,f的定义与2301中的相同，而分块的时候求和需要预处理出来后面那个和式，稍微修改一下线性筛就好

技术分享
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=10000000+2;int N,M,T,prime[MAXN],mu[MAXN],f[MAXN];bool flag[MAXN];void Moebius(ll N){    int cnt=0;    mu[1]=1;    for(int i=2;i<=N;i++){        if(!flag[i]) prime[++cnt]=i,mu[i]=-1;        for(int k=1;k<=cnt && i*prime[k]<=N;k++){            flag[i*prime[k]]=1;            if(i%prime[k]==0){                mu[i*prime[k]]=0;                break;            }            mu[i*prime[k]]=-mu[i];        }    }        for(int i=1;i<=cnt;i++)        for(int j=1;j*prime[i]<=N;j++)            f[j*prime[i]]+=mu[j];    for(int i=2;i<=N;i++) f[i]+=f[i-1];}int main(){    Moebius(MAXN);        cin >> T;    while(T--){        ll ans=0;        scanf("%d %d",&N,&M);        for(int i=1,j;i<=N && i<=M;i=j+1){            j=min(N/(N/i),M/(M/i));            ans+=(ll)(f[j]-f[i-1])*(N/j)*(M/j);        }        printf("%lld",ans);    }    return 0;}
View Code

 

BZOJ2820 YY的GCD 莫比乌斯反演


联系
我们