牛妹的数论题_牛客博客

令 $p=gcd(a,m)$ ,
0≤ $x$ < $m$ ,gcd( $a$ , $m$ )=gcd( $a$ + $x$ , $m$ ).0≤x<m,gcd(a,m)=gcd(a+x,m).
相等的个数等于 $1 \leq x \leq m$ ,gcd( $a$ , $m$ )=gcd( $x$ , $m$ ). $1 \leq x \leq m$ ,gcd(a,m)=gcd(x,m).
然后欧拉定理一下就行了
复杂度O(logm)

#define ll long long
inline ll phi(ll x) 
{
    ll ans = x, y = x;
    for (ll i = 2; i * i <= y; i ++)
        if (x % i == 0) 
        {
            ans /= i, ans *= (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x != 1) ans /= x, ans *= (x - 1);
    return ans;
}
class Solution {
public:
    /**
     * 
     * @param a long长整型 
     * @param m long长整型 
     * @return long长整型
     */
    long long math(long long a, long long m) {
        // write code here
        ll g = __gcd(a, m);
        m /= g;
        return phi(m);
    }
};