题目链接：Same GCDs

题意：给你两个数$a$，$m(1 \leq a < m \leq 10^{10})$，求有多少个$x$满足：$0 \leq x < m$且$gcd(a,m)=gcd(a+x,m)$

思路：设$gcd(a,m)=d$，那么问题转换为求多少个$k \in [a,a+m)$满足$gcd(k,m)=d$

两边同时除$d$，转换为求有多少$k \in [\frac{a}{d},\frac{a+m}{d})$满足$gcd(k,\frac{m}{d})=1$

设$x=\frac{a}{d}$，$y=\frac{m}{d}$，因为$a<m$，所以显然有$x<y$

问题转换为求有多少$k \in [x,x+y)$满足$gcd(k,y)=1$

将区间$[x,x+y)$拆成$[x,y]$和$(y,x+y)$两个区间

  • 考虑区间$(y,x+y)$，$gcd(k,y)=gcd(y,k%y)=gcd(k%y,y)=1$，因为$k \in (y,x+y)$，所以答案为$(0,x)$内与$y$互质的数的个数
  • 考虑区间$[x,y]$，因为$gcd(k,y)=1$，所以答案为$[x,y]$内与$y$互质的数的个数

两个区间一合并，答案就是$\varphi(y)$，即$\varphi(\frac{d}{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
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
int t;
ll a, m;
 
ll gcd(ll a, ll b)
{
    return 0 == b ? a : gcd(b, a % b);
}
 
ll euler(ll n)
{
    ll ans = n;
    for (ll i = 2; i <= sqrt(n); i++) {
        if (0 == n % i) {
            ans = ans / i * (i - 1);
            while (0 == n % i) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
 
int main()
{
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld", &a, &m);
        printf("%lld\n", euler(m / gcd(a, m)));
    }
    return 0;
}