Bzoj 2820: YY的GCD(莫比烏斯反演+除法分塊)

2019-11-06 06:49:49

字體：大中小

供稿：網(wǎng)友

2820: YY的GCD Time Limit: 10 Sec Memory Limit: 512 MB Description 神犇YY虐完數(shù)論后給傻×kAc出了一題給定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)為質(zhì)數(shù)的(x, y)有多少對kAc這種傻×必然不會了，于是向你來請教……多組輸入 Input 第一行一個整數(shù)T 表述數(shù)據(jù)組數(shù)接下來T行，每行兩個正整數(shù)，表示N, M Output T行，每行一個整數(shù)表示第i組數(shù)據(jù)的結(jié)果 Sample Input 2 10 10 100 100 Sample Output 30 2791 HINT T = 10000 N, M <= 10000000

這里寫圖片描述 Here 基本上還是看懂了的….

/*莫比烏斯.最后用除法分塊..篩莫比烏斯函數(shù)部分:顯然每個素數(shù)直接計算mu[i]=-1.我們知道莫比烏斯函數(shù)值是(-1)^k,k是互異質(zhì)數(shù)的個數(shù).對于一個合數(shù)x,令它質(zhì)因子的最小的那個為p1,則有x=p1*t1,另設(shè)一個與異于p1的質(zhì)因子為p2.則有p1*t1=p2*t2.因為p1與p2互素,所以p2|t1,p1|t2.所以當i枚舉到t2時,因為p1|t2,所以退出**有一個疑問:就是如果有一個數(shù)x1>x,那直接退出以后是不是會影響x1函數(shù)值的計算???數(shù)學不好沒證出來orz**假如有一個x1=t1*p,且p是x1最大的質(zhì)因數(shù).當i枚舉到t1時,計算一下x的函數(shù)值.所以我們保證算的每一個合數(shù)的莫比烏斯函數(shù)的時候都是在最后一個計算素數(shù)的時候的即每個函數(shù)值都只計算了一次.復(fù)雜度是O(n)噠.*/#include<iostream>#include<cstdio>#define MAXN 10000001#define LL long longusing namespace std;int mu[MAXN],PRi[MAXN],tot,g[MAXN],sum[MAXN],last;LL ans,n,m;bool vis[MAXN];void pre(){ mu[1]=1; for(int i=2;i<=MAXN-1;i++) { if(!vis[i]) pri[++tot]=i,mu[i]=-1,g[i]=1; for(int j=1;j<=tot&&i*pri[j]<=MAXN-1;j++) { vis[i*pri[j]]=true; if(i%pri[j]) mu[i*pri[j]]=-mu[i],g[i*pri[j]]=mu[i]-g[i]; else { mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break; } } } for(int i=1;i<=MAXN-1;i++) sum[i]=sum[i-1]+g[i];}int main(){ int t,x,y;pre(); scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&m); if(n>m) swap(n,m); ans=0; for(LL i=1;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]); } printf("%lld/n",ans); } return 0;}

上一篇：Spring AOP介紹

下一篇：nodejs udp組播通信(未完)