codeforces-Ed81-D

codeforces-Ed81-D

七月 08, 2020

D.Same GCDs

题意
求有多少x符合gcd(a+x,m)=gcd(a,m)=gcd;
且m>x>=0;
直接求phi[m/gcd(a,m)];
存在gcd(y,m)=gcd(a,m) y<a:
但由于a+x>m,
gcd(y,m)=gcd(y+m,m) (更相减损术)
y+m>=a且 y+m<a+m

[a,a+m]中总有一个数z可以通过更相减损变成y

所以问题变成了有多少个y<a 使得gcd(y,m)=gcd(a,m)

这里用到一个性质gcd(y,m)=gcd(a,m)=d -> 两边同除d -> gcd(y,m/d)=1

那问题又从有多少个y<a 使得gcd(y,m)=gcd(a,m) 变成了有多少个 小于m/gcd(a,m)的数与m/gcd(a,m)互质 这个就是欧拉函数所表示的 phi [n]= 有多少个[i<n] gcd(i,n)==1

即1到m/gcd(a,m)中与m/gcd(a,m)互质的个数 == phi[m/gcd(a,m)]

gcd(y,m)==gcd的数量其实就是 gcd(a+x,m) ==gcd (a+x>=m) 的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define IO std::ios::sync_with_stdio(false);

# define endl '\n'

string s,t;
//int de[(int)1e5+5];
int main() {
    int T;cin>>T;
    while(T--){
        ll a,m;cin>>a>>m;
        ll gcd=__gcd(a,m);
        a/=gcd;m/=gcd;
        ll ans=m;
        for(ll i=2;i*i<=m;i++){
            if(m%i==0){
                ans-=ans/i;///1~m中有ans/i个数是i的倍数
                while(m%i==0)m/=i;///将m中的因子i剔除
            }
        }
        if(m>1)ans-=ans/m;
        cout<<ans<<endl;
    }
}