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

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology