[TIOJ] 1875. 解咒
題目連結: http://tioj.infor.org/problems/1875 雖然題目敘述不知道是在講什麼鬼，但他其實就是一題裸的歐拉函數題，根據維基百科上的資料可以知道歐拉函數可以推導成$\displaystyle \varphi (n) = \prod _{{p\mid n}}p^{{\alpha _{p}-1}}(p-1) $，同時把篩法的概念套入後就發現，其實就是$ \forall 2 \leq i \leq \sqrt{n} $，重複將$n$除以$i$直到除不盡為止，在將回傳直乘以$i-1$。 #include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const lld N = 600000000;
inline lld Euler(lld);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
lld x;
while(cin>>x){
if(x>N) cout<<x-1<<'\n';
else cout<<Euler(x)<<'\n';
}
return 0;
}
inline lld Euler(lld x){
lld r=1;
for(lld i=2;i*i<=x;++i){
if(x%i==0){
x/=i;
r*=(i-1);
while(x%i==0){
x/=i;
r*=i;
}
}
}
if(x>1) r*=x-1;
return r;
}