达达正在破解一段密码,他需要回答很多类似的问题:
对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。
作为达达的同学,达达希望得到你的帮助。
输入格式
第一行包含一个正整数n,表示一共有n组询问。
接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。
输出格式
对于每组询问,输出一个正整数,表示满足条件的整数对数。
数据范围
1≤n≤500001≤n≤50000,
1≤d≤a,b≤500001≤d≤a,b≤50000
输入样例:
2
4 5 2
6 4 3
输出样例:
3
2
提示:gcd(x,y)返回x,y的最大公约数。
题意:满足题目所给的式子的x,y对数
思路:莫比乌斯反演
这里就我也不自己写一遍了,贴一篇大牛写的博客,也是看这个学习的,性质证明,公式证明都有
https://blog.csdn.net/outer_form/article/details/50588307
今天有点累了,就不写自己的推理的(偷懒 >_<)
来个大牛博客:https://blog.csdn.net/ycdfhhc/article/details/50637101
#include<bits/stdc++.h> #define maxn 50005 #define mod 1000000007 using namespace std; typedef int ll; ll a,b,k; ll vis[maxn+10]; ll mu[maxn+10]; ll sum[maxn+10]; void init(){ for(int i=1;i<maxn;i++){ vis[i]=0; mu[i]=1; } for(int i=2;i<maxn;i++){ if(vis[i]==0){ mu[i]=-1; for(int j=2*i;j<maxn;j+=i){ vis[j]=1; if((j/i)%i==0) mu[j]=0; else mu[j]=-mu[j]; } } } sum[1]=1; for(int i=2;i<maxn;i++){ sum[i]=sum[i-1]+mu[i]; } } ll g(ll x,ll y){ ll num=0; ll l=1,r=0; if(x>y) swap(x,y); for(;l<=x;l=r+1){ r=min(x/(x/l),y/(y/l)); num+=(sum[r]-sum[l-1])*(x/l)*(y/l); //cout<<l<<" "<<r<<" "<<num<<endl; } return num; } int main(){ init(); int t; scanf("%d",&t); while(t--){ scanf("%d%d%d",&a,&b,&k); ll num=g(a/k,b/k); printf("%d ",num); } }