首页 > 代码库 > Bzoj1101 [POI2007]Zap
Bzoj1101 [POI2007]Zap
Submit: 2414 Solved: 995
[Submit][Status][Discuss]
Description
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a
,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。
Input
第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个
正整数,分别为a,b,d。(1<=d<=a,b<=50000)
Output
对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。
Sample Input
2
4 5 2
6 4 3
4 5 2
6 4 3
Sample Output
3
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,3)。
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,3)。
HINT
Source
数学问题 莫比乌斯反演 分块
当然可以化成
所以我们要求的变成下面这个:
为了表示方便,重新赋值a=a/d,b=b/d
下文开始,d用作莫比乌斯函数的记号,与题目给出的d无关
利用莫比乌斯函数的性质把上式化成:
由于d|gcd(i,j)等价于 (d|i) && (d|j)
上式化成:
也就是
发现d取值在一个连续区间时,a/d的结果是相同的,所以可以用分块的方式,将a/d结果相同的一个区间放在一起算。
而这段区间内的μ(d)可以通过求前缀和得到
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=50011; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int pri[mxn],cnt=0;16 int mu[mxn],smm[mxn];17 bool vis[mxn];18 void init(){19 mu[1]=1;20 for(int i=2;i<mxn;i++){21 if(!vis[i]){pri[++cnt]=i;mu[i]=-1;}22 for(int j=1;j<=cnt && pri[j]*i<mxn;j++){23 vis[pri[j]*i]=1;24 if(i%pri[j]==0){25 mu[i*pri[j]]=0;26 break;27 }28 mu[i*pri[j]]=-mu[i];29 }30 }31 for(int i=1;i<mxn;i++)smm[i]=smm[i-1]+mu[i];32 return;33 }34 int clc(int n,int m){35 if(n>m)swap(n,m);36 int res=0,pos=0;37 for(int i=1;i<=n;i=pos+1){38 int x=n/i,y=m/i;39 pos=min(n/x,m/y);40 res+=(smm[pos]-smm[i-1])*x*y;41 }42 return res;43 }44 int main(){45 int i,j,a,b,d;46 init();47 int T=read();48 while(T--){49 a=read();b=read();d=read();50 int ans=clc(a/d,b/d);51 printf("%d\n",ans);52 }53 return 0;54 }
Bzoj1101 [POI2007]Zap
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。