[PS] GCD(n, k) = 1 / C++ (백준 11689번)

 

 

1~$10^{12}$ 범위인 N과 서로수인 수의 개수를 구하는 문제

 

깡으로 하면 무조건 시간 초과이므로 오일러 피 함수의 성질을 이용해서 풀 수 있다. 

오일러 피 함수 성질

 

시행 착오

에라토스테네스의 체로 소수를 모두 구별하여 N을 소인수분해 한 뒤, 오일러 피 함수의 성질을 이용하여 답을 도출하는 식으로 구상했지만, $10^{12}$ 이하의 가장 큰 소수가 999999999989이므로 당연히 메모리 초과가 나왔다.

 

해답

사실 2부터 시작해서 N의 값을 나눌 수 있을 때까지 나누면 소수를 따로 구할 필요없이 소수로만 나눌 수 있다.

나눌 때마다 오일러 피 함수의 성질을 이용하여 변수를 지정해 곱해놓으면 답을 구할 수 있다.

 

※ N=99처럼 sqrt(N)보다 N의 약수(11)가 더 큰 경우가 있으므로 이 경우엔 N이 1까지 나눠지지 못했기 때문에 마지막에 예외처리를 해주어야 함 

 

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;

int main()
{
	pair<ll, ll> pa = make_pair(0, 0);
	ll n, dap = 1;
	scanf("%lld", &n);
	int sqrt_n = sqrt(n);
	for (ll i = 2; i <= sqrt_n; i++) {
		if (n % i == 0) {
			int c = 0;
			while (n % i == 0) {
				n /= i;
				c++;
			}
			dap *= pow(i, c - 1) * (i - 1);
		}
	}
	if (n > 1) {
		dap *= n - 1;
	}

	printf("%lld\n", dap);
	return 0;
}