,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。

输入样例：

1
2
3
4
3
4 9
5 10
42 9999999967

输出样例：

1
2
3
6
1
9999999966

题目思路

我们首先需要化简题目：题目求的其实是 有多少x满足 x 大于零，且小于m，并且(a+x)/gcd(a,m)和m/gcd(a,m)互质。

这个题目我们可以分部分化简，

  1. a + x <= m

    这个情况下，我们其实就是求 a / gcd(a,m) 到 (a+m)/gcd(a,m) 中间有多少数字和(a+m)/gcd(a,m)互质。

  2. a + x > m

    这个情况我们求(a+m)/gcd(a,m) 到 (a + m) / gcd(a,m) 中间有多少数字和(a+m)/gcd(a,m)互质。

    也就是求x 属于(0,m) ,gcd( (a+x)/gcd(a,m) , m/gcd(a,m)) = 1的数字个数。

    其实我们有一个概念需要知道，根据辗转相除法求最大公约数的原理，我们可以知道gcd(x,y) = gcd(x - y,y)

    所以我们其实可以转化成求求x 属于(0,m) ,gcd( (a+x-m) - m/gcd(a,m) , m/gcd(a,m)) = 1的数字个数。

    这部分求得就是1 / gcd(a,m) 到 (a)/gcd(a,m) 中间有多少数字和(a+m)/gcd(a,m)互质。

最后其实这样求得就是m/gcd(a,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
class Main{
    public static Scanner sc = new Scanner(System.in);
    
    public static long gcd(long a,long b){
        if(a < b){
            long temp = a;
            a = b;
            b = temp;
        }
        return b == 0 ? a : gcd(b,a%b);
    }
    
    public static void main(String[] args){
        int k = sc.nextInt();
        while((k--)!=0){
            long a = sc.nextLong(),b = sc.nextLong();
            long g = gcd(a,b);
            
            long l = a / g,r = b / g;
            long eul = r,temp = r;
            for(long i = 2;i <= temp / i;i++){
                long index = 0;
                while(temp % i == 0){
                    temp /= i;
                    index = 1;
                }
                if(index == 1) eul = eul / i * (i - 1);
            }
            if(temp > 1) eul = eul / temp * (temp - 1);
            System.out.println(eul);
        }
    }
}