백준 BOJ 11689 - GCD(n, k) = 1

오일러 피 함수의 구현

오일러 피 함수는 주어진 수를 소인수분해한뒤

소인수분해된 수들을 다음과 같은 규칙에 따라 계산하면 된다

 

P(소수) = A^a * B^b * C^c ......

 

f(P) = (A^a - A^(a-1) * (B^b - B^(b-1)) ......

 

그럼 이제 이 문제는 주어진 수를 빠르게 소인수분해하는 문제가 된다.

 

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

map<ll,ll> prime;

int main(){
	ll n;
	ll ans = 1;
	scanf("%lld", &n);
	if(n==1){ printf("1"); return 0; }
	
	ll k = 2;
	while(k*k <= n){
		if(n%k == 0){
			prime[k]++;
			n /= k;
			continue;
		}
		k++;
	}
	prime[n]++;
	
	for(auto it=prime.begin(); it!=prime.end(); it++){ ans *= ((ll)pow(it->first, it->second) - (ll)pow(it->first, it->second-1)); }
	printf("%lld", ans);
	return 0;
}