[C++] 백준 11689: GCD(n, k) = 1

문제

[C++] 백준 11689: GCD(n, k) = 1 GOLD 1
https://www.acmicpc.net/problem/11689

 

---

 

접근 방법

이 문제는 어떤 수 n에 대해, 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 구하는 문제다.

이는 곧 오일러 피 함수 φ(n)를 구하는 문제이고, 공식을 이용하면 다음처럼 쓸 수 있다.

여기서

• p∣n 은 “p가 n의 약수(소인수)”라는 뜻
• 곱은 “n의 서로 다른 소인수들”에 대해서만 한 번씩 해주면 된다.

즉,

1. n을 소인수분해해서 서로 다른 소인수 p 들을 찾고
2. ret에 ret = ret * (1 - 1 / p)를 순서대로 적용해 주면 최종적으로 ret이 φ(n)이 된다.

이 공식을 그대로 구현하면, n이 최대 범위일 때도 O(√n) 안에 해결할 수 있다.

 

상세 아이디어

1. n과 ret 역할 분리

코드에서 변수 두 개를 이렇게 둔다.

LL n;      // 입력 받은 수, 소인수를 제거해 가며 줄여나가는 용도
LL ret = n; // 실제로 φ(n)을 계산해서 담아둘 결과 변수

• n은 소인수분해용 “재료”
  → p로 나눠지면 계속 나누면서 점점 작아진다.
• ret은 오일러 피 함수 결과를 저장하는 변수
  → 소인수 p를 찾을 때마다
  ret = ret - ret / p 로 값을 줄여나간다.

 

2. 소인수 p 찾기 + 오일러 피 공식 적용

반복문으로 작은 수부터 차례대로 나눠보며 n의 소인수를 찾아간다.

for (LL p = 2; p <= sqrt(n); p++)
{
    if (n % p == 0)  // p가 n을 나누면, p는 n의 소인수
    {
        ret = ret - (ret / p); // ret *= (1 - 1/p)와 같은 의미

        while (n % p == 0)     // 같은 소인수를 중복 처리하지 않기 위해
            n /= p;            // n에서 p를 모두 제거
    }
}

여기서 중요한 포인트:

• ret = ret - ret / p
  → ret *= (1 - 1/p)를 정수 연산으로 바꾼 것
  → “p의 배수들은 φ(n) 후보에서 빠져야 한다”는 의미 (에라토스테네스의 체 원리와 유사하다.)
• while (n % p == 0) n /= p;
  → n에서 소인수 p를 가능한 만큼 다 나눠서 제거
  → 같은 p를 다시 만나서 또 한 번 더 ret = ret - ret / p 를 적용하지 않도록 하는 역할
  → 오일러 피 공식은 “서로 다른 소인수”마다 한 번씩만 적용해야 하기 때문

 

3. 마지막 남은 소인수 처리

반복문이 끝난 뒤에도 n이 1보다 크면, 그 값 자체가 마지막 소인수(또는 소수)로 남아 있는 상태다.

예를 들어,

• 처음 n이 12라면
  • p = 2, 3이 처리되고
  • 마지막 n은 1이 된다.
• 처음 n이 17(소수)라면
  • for문에서 어떤 p도 n을 나누지 못하고
  • 마지막에 그대로 n = 17이 남아 있다.

즉, 반복문에서 제곱근까지만 탐색했기 때문에 1개의 소인수가 누락되는 케이스이다.

이런 경우를 처리하기 위해 다음 코드를 추가한다.

if (n > 1)
    ret = ret - (ret / n);

이 한 줄로, 마지막으로 남은 소인수 n에 대해서도 ret *= (1 - 1/n) 을 적용해주는 셈이다.

 

구현 시 주의할 점

• 자료형은 반드시 long long 사용하기 (LL)
  • 입력 n의 범위가 크기 때문에, int로는 오버플로우가 날 수 있다.
• n과 ret 역할을 헷갈리지 않기
  • n → 소인수분해를 위해 계속 나눠서 줄이는 “작업용” 값
  • ret → 오일러 피 함수의 결과를 담는 값
  • while (n % p == 0) n /= p;에서 나누는 대상은 항상 n이다.
    여기서 ret을 나누면 안 된다.
• 같은 소인수에 대해 한 번만 φ(n) 공식 적용하기
  • while (n % p == 0)로 소인수 p를 n에서 완전히 제거한 뒤,
    다시는 같은 p에 대해 ret = ret - ret / p가 실행되지 않도록 한다.
  • 그렇지 않으면 (1 - 1/p)를 여러 번 곱하는 꼴이 되어 잘못된 결과가 나온다.
• 루프 조건에서 sqrt(n) 사용 시 주의
  • 여기서는 for (LL p = 2; p <= sqrt(n); p++)처럼 썼는데,
    반복문 안에서 n이 줄어들기 때문에 sqrt(n) 값도 함께 줄어든다.
  • 이는 오히려 연산량을 줄여주는 효과가 있고,
    마지막에 if (n > 1)에서 남은 소인수를 처리하므로 소인수를 놓치는 일은 없다.

 

---

 

코드

#include <iostream>
#include <cmath>
using namespace std;

typedef long long LL;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	LL n = 0;
	cin >> n;
	
	LL ret = n;
	for (LL p = 2; p <= sqrt(n); p++)
	{
		if (n % p == 0)  // p가 소인수라면
		{
			ret = ret - (ret / p);

			while (n % p == 0)  // 해당 소인수 지우기
				n /= p;
		}
	}
	if (n > 1)
		ret = ret - (ret / n);

	cout << ret;
}