백준 BOJ 19577 - 수학은 재밌어

오일러 피 함수의 구현과 그 응용 문제

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

19577번: 수학은 재밌어

모든 수에 대해서 xF(x) 를 구하려 하면 TLE 가 발생한다.

이를 해결하기 위해서는 x도 정수, F(x)도 정수임을 이용해

x에 들어갈 수를 N의 약수로 한정지으면 문제를 해결할 수 있다.

 

그리고 N==1일때 코너케이스가 발생해 이부분을 따로 처리해주었다.

 

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

map<ll,ll> prime;
vector<ll> v;

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