math/euler.hpp

• View this file on GitHub
• Last update: 2023-03-13 22:17:07+09:00
• Include: #include "math/euler.hpp"

Verified with

• test/aoj/NTL/NTL_1_D.test.cpp

Code

ll euler(ll n){
  ll res = n, k = n;
  for(ll i = 2; i*i <= k; i++){
    if(n % i) continue;
    res = res / i * (i - 1);
    while(n % i == 0) n /= i;
  }
  if(n != 1) res = res / n * (n - 1);
  return res;
}

#line 1 "math/euler.hpp"
ll euler(ll n){
  ll res = n, k = n;
  for(ll i = 2; i*i <= k; i++){
    if(n % i) continue;
    res = res / i * (i - 1);
    while(n % i == 0) n /= i;
  }
  if(n != 1) res = res / n * (n - 1);
  return res;
}

Back to top page