This documentation is automatically generated by online-judge-tools/verification-helper
#include "math/totient.hpp"
#pragma once
#include "math/prime_factor.hpp"
long long totient(long long n) {
auto pf = prime_factor(n);
for (auto &[p, e] : pf) {
n /= p;
n *= p - 1;
}
return n;
}
#line 2 "math/totient.hpp"
#line 2 "math/prime_factor.hpp"
std::map<long long, int> prime_factor(long long n) {
std::map<long long, int> res;
for (long long i = 2; i * i <= n; i++) {
while (n % i == 0) {
res[i]++;
n /= i;
}
}
if (n != 1) res[n]++;
return res;
}
#line 4 "math/totient.hpp"
long long totient(long long n) {
auto pf = prime_factor(n);
for (auto &[p, e] : pf) {
n /= p;
n *= p - 1;
}
return n;
}