本文共 1686 字,大约阅读时间需要 5 分钟。
Same GCDs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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≤501≤T≤50) — the number of test cases.
Next T lines contain test cases — one per line. Each line contains two integers a and mm (1≤a<m≤10101≤a<m≤1010).
Output
Print T integers — one per test case. For each test case print the number of appropriate x-s.
Example
input
Copy
34 95 1042 9999999967
output
Copy
619999999966
Note
In the first test case appropriate x-s are [0,1,3,4,6,7][0,1,3,4,6,7].
In the second test case the only appropriate x is 00.
题意:给定a和m,求满足gcd(a,m) = gcd(a+x,m)的x数量
题解:首先引出一个原理:gcd(a,b) = gcd(a-b,b)。由此我们可以得到当a+x>=m时,gcd(a+x,m)=gcd(a+x-m,m)。令x' = (a+x)%m,我们可以得知最多有m个不同的x',也就是说x\(\in\)[0,m-1]。问题也就转换成了gcd(a,m) = gcd(x',m)。下面我们令gcd(a,m) = y,令a = ya',m = ym',gcd(a,m) = gcd(ya',ym') = y*gcd(a',m'),可得a'与m'互质,再令x' = yx'',同上,也就是x''与m'互质,同时因为gcd(0,m') = m'>1,得出x''\(\in\)[1,m'-1],根据这个定义,我们可以明白该题的目的就是求出m'内所有与m'互质的数,即m'的欧拉函数
如何求m'的欧拉函数,\(\varphi\)(m') = m'\(\prod_{i=1}^l{(1-{1\over{p_i}})}\),m'直接利用gcd(a,m)即可求出
代码:
#include#include #include #include #include #include #include #include #include
转载地址:https://www.cnblogs.com/cloudplankroader/p/12256412.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!