给定两个正整数 $a,m$,其中 $a < m$。
请你计算,有多少个小于 $m$ 的非负整数 $x$ 满足:
$gcd(a,m) = gcd(a+x,m)$
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据占一行,包含两个整数 $a,m$。
输出格式
每组数据输出一行结果,一个整数,表示满足条件的非负整数 x$x$ 的个数。
数据范围
前三个测试点满足,$1 \le T \le 10$。
所有测试点满足,$1 \le T \le 50$,$1 \le a < m \le 10^{10}$。
输入样例:
3
4 9
5 10
42 9999999967
输出样例:
6
1
9999999966
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while (T --)
{
long long a, m;
cin >> a >> m;
long long g = __gcd(a, m);
m /= g; // 将 m 缩小至与 a 互质
// 统计小于 m 且与 a 互质的数的个数
long long result = m;
for (long long i = 2; i * i <= m; i ++)
{
if (m % i == 0)
{
while (m % i == 0) m /= i;
result -= result / i;
}
}
if (m > 1) result -= result / m;
cout << result << '\n';
}
return 0;
}