オイラーのトーシェント関数 (φ, ファイ, phi)

1800 ライブラリ

verified

// 借り物
// https://ei1333.github.io/luzhiled/snippets/math/euler-phi.html
int64_t euler_phi(int64_t n) {
  int64_t ret = n;
  for(int64_t i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ret -= ret / i;
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ret -= ret / n;
  return ret;
}

// 1 to n までのnと互いに素である個数
ll eulers_totient_function(ll n){
  ll n_original = n;
  // 10^10まで可能
  VI P;
  for(ll i=2; i*i<=n; i++){
    if(n%i==0){
      P.push_back(i);
    }
    while(n%i==0) n/=i;
  }
  P.push_back(n);
  // 素因数を使って実際に求める
  n = n_original;
  for(ll p : P){
    if(p==1) continue; // 盲点
    n -= n/p;
  }
  return n;
}

void solve(){
  ll a,m;cin>>a>>m;
  ll g = gcd(a,m);
  ll n = m/g;

  ll ans = eulers_totient_function(n);
  // ll ans = euler_phi(n);

  p(ans);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}