Description:
You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m).
Note: gcd(a,b) is the greatest common divisor of a and b.
Input
The first line contains the single integer T(1≤T≤50) — the number of test cases.
Next T lines contain test cases — one per line. Each line contains two integers a and m(1≤a<m≤1010).
Output
Print T integers — one per test case. For each test case print the number of appropriate x−s.
Example
input
3
4 9
5 10
42 9999999967
output
6
1
9999999966
Note
In the first test case appropriate x−s are [0,1,3,4,6,7].
In the second test case the only appropriate x is 0.
题意:
给出两个正整数 a 和 m ,再给出 x 的范围为[0,m),现在要求满足 gcd(a,m)=gcd(a+x,m) 时 x 的个数。
首先提取 a 和 m的最大公约数 g,令 a=xg,m=yg
题意就可转化为需要使得 gcd(xg,yg)=gcd(xg+z,yg)=g
显然可知 z为 g 的倍数,令 z=kg,k∈[0,y)
那么所有满足 gcd(x+k,y)=1的 k 都可以,即求 [x,x+y) 中与 y 互素数的个数。
因为 gcd(x,y)=gcd(y,y%x),故当 x+k∈(y,x+y) 时,gcd(x+k,y)=gcd(y,(x+k)%y),
因为 x<y,k∈[0,y) ,所以 gcd(x+k,y)=gcd(y,(x+k)−y)=1
而 x+k−y∈(0,x)
所以 (y,x+y) 中与 y 互素数的个数与 (0,x) 中与与 y 互素数的个数相等。
所以答案就是 [1,y] 中与 y 互素数的个数。
邵光亮 发布了611 篇原创文章 · 获赞 390 · 访问量 20万+ 关注