2021-10-16最大公约数

给定两个正整数 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级别,懒得搞了

2021-10-16最大公约数

#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;
    }
}

上一篇:虹科案例 | 新突破!虹科AR眼镜助力美国首例全膝关节置换手术


下一篇:7.6上课笔记以及作业