我们定义 $d = \gcd(a, m)$,那么就可以得到:
$$d | a, d | (a + x)$$
进而可得 $d | x$。
我们又定义 $a’ = \dfrac{a}{d}, m’ = \dfrac{m}{d}, x’ = \dfrac{x}{d}$,那么根据最大公约数的性质,可得:
$$\gcd(a’ + x’, m’) = 1$$
而题目就转化为了:求 $[a’, a’ + m’ - 1]$ 中有几个数与 $m’$ 互质。
同时由于 $0 \leq x < m$,所以 $0 \leq x’ < m’$(同时除了一个数,大小关系不变)。
因为 $[0, a’ - 1]$ 中在模 $m$ 的意义下的余数与 $[m’, a’ + m’ - 1]$(也可理解为 $[m’, m’ + a’ - 1]$)中在模 $m$ 的意义下的余数一致,可得 $[0, a’ - 1]$ 中与 $m$ 互质的数与 $[m’, a’ + m’ - 1]$ 中与 $m$ 互质的数一样;进而,根据「同增同减差不变」原理,可得:$[0, m’ - 1]$ 中与 $m$ 互质的数与 $[a’, a’ + m’ - 1]$ 中与 $m$ 互质的数一样(「同增」了 $[a’, m’ - 1]$ 这一段),而这个「等式」的右项正好是我们要求的答案,左项就是要用欧拉函数的flag,结果就是 $\varphi(m’)$,所以我们输出 $\varphi(m’)$ 即可
*注:为了防止出现歧义,此处统一定义 $x | y$ 的意思为 $y \bmod x = 0$
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
const LL INF = 0x3f3f3f3f, INF_BIT = 0x3f;
const LL N = 1e5 + 10;
LL t;
LL a, m;
LL gcd(LL a, LL b){
return b ? gcd(b, a % b) : a;
}
LL phi(LL x){
LL ret = x;
for(LL i = 2;i <= x / i;i++)
if(x % i == 0){
ret -= ret / i;
while(x % i == 0)
x /= i;
}
if(x != 1) ret -= ret / x;
return ret;
}
int main(){
scanf("%lld", &t);
while(t--){
scanf("%lld%lld", &a, &m);
LL t = gcd(a, m);
a /= t, m /= t;
printf("%lld\n", phi(m));
}
return 0;
}