https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98
이걸 구현하면 된다.
n이 최대 10^12이므로 루트n까지 시도하고 숫자가 남아있으면 걔도 소인수니까 마지막에 계산해주면 됨.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long n;
cin >> n;
long long ans = n;
for (long long i = 2; i*i <= n; i++) {
if (n%i == 0) {
ans -= ans/i;
while (n%i == 0) n/=i;
}
}
if (n != 1) {
ans -= ans/n;
}
cout << ans;
return 0;
}
long long i
저 전역 3주 남음 ㅎㅎ