[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;
}