首页 > 代码库 > BZOJ 2820: YY的GCD [莫比乌斯反演]【学习笔记】
BZOJ 2820: YY的GCD [莫比乌斯反演]【学习笔记】
2820: YY的GCD
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1624 Solved: 853
[Submit][Status][Discuss]
Description
神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了，于是向你来请教……多组输入
Input
第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M
Output
T行，每行一个整数表示第i组数据的结果
Sample Input
2
10 10
100 100
10 10
100 100
Sample Output
30
2791
2791
HINT
T = 10000
N, M <= 10000000
和bzoj2705很像http://www.cnblogs.com/candy99/p/6200745.html
但是n和m不同，不能使用直接欧拉函数的方法
参考：http://blog.csdn.net/acdreamers/article/details/8542292 && popoqqq课件
和上一题相同的函数：
显然
可以枚举每一个质数，套用上一题的做法，p相当于k，d*p也就是p的倍数了...很像上一题我WT1中的式子
其实d只要枚举到min(n,m)/p
然而复杂度承受不了，大约n/logn*sqrt(n)
我们设
为什么这么做呢？因为这样之后发现F函数与p和d无关了，(要不然枚举p和d也是枚举了T)
可以提到前面，剩下的那一块可以处理前缀和做到O(1)，前面再用除法分块，做到O(sqrt(n))
WT:
如何求g(T)=Σ{p|T && isprime(p)}miu(T/p)
法1.
只需要枚举每个素数暴力就行了
由于有1/1+1/2+1/3+...+1/n=O(logn)这个结论 因此每个质数枚举时是均摊O(logn)的
而质数恰好有O(n/logn)个 因此暴力枚举就是O(n)的
法2.
线性筛
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=1e7+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,m;bool notp[N];int p[N],mu[N],g[N];void sieve(){ mu[1]=1; for(int i=2;i<N;i++){ if(!notp[i]) p[++p[0]]=i,mu[i]=-1; for(int j=1;j<=p[0]&&i*p[j]<N;j++){ notp[i*p[j]]=1; if(i%p[j]==0){ mu[i*p[j]]=0; break; } mu[i*p[j]]=-mu[i]; } } for(int j=1;j<=p[0];j++) for(int i=p[j];i<N;i+=p[j]) g[i]+=mu[i/p[j]]; for(int i=1;i<N;i++) g[i]+=g[i-1];}ll cal(int n,int m){ if(n>m) swap(n,m); ll ans=0;int r; for(int i=1;i<=n;i=r+1){ r=min(n/(n/i),m/(m/i)); ans+=(ll)(g[r]-g[i-1])*(n/i)*(m/i); } return ans;}int main(int argc, const char * argv[]) { sieve(); int T=read(); while(T--){ n=read();m=read(); printf("%lld\n",cal(n,m)); } return 0;}
BZOJ 2820: YY的GCD [莫比乌斯反演]【学习笔记】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。