给定两个正整数 a,m,其中 a<m
。
请你计算,有多少个小于 m
的非负整数 x
满足:
gcd(a,m)=gcd(a+x,m)
输入格式
第一行包含整数 T
,表示共有 T
组测试数据。
每组数据占一行,包含两个整数 a,m
。
输出格式
每组数据输出一行结果,一个整数,表示满足条件的非负整数 x
的个数。
数据范围
前三个测试点满足,1≤T≤10
。
所有测试点满足,1≤T≤50,1≤a<m≤1010
。
输入样例:
3
4 9
5 10
42 9999999967
输出样例:
6
1
9999999966
使用容斥原理求一段区间与Q互斥的数的个数
构建质因子集合可以优化到logn级别,懒得搞了
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1e6+10;
int prime[N],cnt=0;
bool p[N];
long long ar[100];
void build(long long x)
{
ar[0]=0;
for(int i=1;i<=cnt;i++)
{
if(x%prime[i]==0)
{
ar[++ar[0]]=prime[i];
while(x%prime[i]==0) x/=prime[i];
}
}
if(x!=1) ar[++ar[0]]=x;
}
long long cal(int len,int con,long long mul,long long x)
{
long long ans=0;
if(len>ar[0])
{
if(mul==1) return 0;
int f=1;
if(~con&1) f=-1;
ans+=x/mul*f;
return ans;
}
ans+=cal(len+1,con+1,mul*ar[len],x);
ans+=cal(len+1,con, mul ,x);
return ans;
}
int main()
{
for(int i=2;i<N;i++)
{
if(!p[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<N;j++)
{
p[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
int t;
cin>>t;
while(t--)
{
long long a,b,G,P,Q;
cin>>a>>b;
G=__gcd(a,b);
P=a/G,Q=b/G;
build(Q);
long long ans=0;
long long y1=0,y2=0;
y1=cal(1,0,1,P+Q-1);
y2=cal(1,0,1,P-1);
ans=Q-y1+y2;
cout<<ans<<endl;
}
}