首页 > 代码库 > 双亲数 容斥
双亲数 容斥
小D是一名数学爱好者,他对数字的着迷到了疯狂的程度。
我们以d = gcd(a, b)表示a、b的最大公约数,小D执著的认为,这样亲密的关系足可以用双亲来描述,此时,我们称有序数对(a, b)为d的双亲数。
与正常双亲不太相同的是,对于同一个d,他的双亲太多了 >_<
比如:(4, 6), (6, 4), (2, 100)都是2的双亲数。
于是一个这样的问题摆在眼前,对于0 < a <= A, 0 < b <= B,有多少有序数对(a, b)是d的双亲数?
题意就是求满足0<x<=N,0<y<=M,gcd(x,y)=d的点对数量;
设f[i]为gcd(x,y)=i的点对数量,根据乘法原理可得满足i|gcd(x,y)的点对数量为(n/i)*(m/i),我们只需要将后面的数量减去sum(f[d*i]),d>=2,d*i<=min(n,m);
这就是个从后向前的递推,时间复杂度是O(nlogn);
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cstdlib>#include<ctime>#include<vector>#include<algorithm>#include<queue>#include<map>using namespace std;#define LL long longint n,m,d;LL f[1010000];void init(){ scanf("%d%d%d",&n,&m,&d); LL sum=0; if(n>m)swap(n,m); for(int i=n/d*d;i;i-=d){ f[i]=((LL)n/i)*((LL)m/i); for(int j=i<<1;j<=n;j+=i)f[i]-=f[j]; } cout<<f[d]<<endl; }int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); init(); return 0;}
双亲数 容斥
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。