D. Same GCDs

題目連結：D. Same GCDs

time limit per test:2 seconds memory limit per test:256 megabytes inputstandard input outputstandard 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≤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.

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。從[a，a+m)中取出任意一個數x，使得gcd(x,m)=gcd(a,m)成立，問你這樣的的x的個數一共有幾個。

解題思路

我們設 p=gcd(a,m); 則p=gcd(x,m);然後同時除以p得1=gcd(x/p,m/p);這時候我們發現其實要求的的也就是[a/p,a/p+m/p)中與m/p互質的數有幾個。同時減去a/p的，也就是[1,m/p)中于m/p互質的的個數，直接用歐拉函數就可以了；

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    int t;
    ll a,m;
    cin>>t;
    while(t--)
    {
        cin>>a>>m;
        ll p=__gcd(a,m);
        ll ans=m/p;
        ll q=ans;
        //歐拉函數
        for(ll i=2;i*i<=q;i++)
        {
            if(q%i==0) ans=ans-ans/i;
            while(q%i==0) q/=i;
        }
        if(q!=1) ans-=ans/q;
        cout<<ans<<"\n";
    }
    return 0;
}           

複制