Python으로 서로소인 두 수의 곱이 x가 되는 쌍의 개수 찾기

문제 개요

함수 f(x)가 있다고 가정해 보겠습니다. 이 함수는 아래 조건을 모두 만족하는 (p, q) 쌍의 개수를 세는 역할을 합니다.

• 1 < p <= q <= x
• p와 q는 서로소 (최대공약수가 1)
• p × q = x

하나의 숫자 n이 주어지면, 1부터 n까지의 모든 x에 대해 f(x) 값의 합을 구해야 합니다.

예를 들어 입력이 12라면 결과는 3이 됩니다. x의 범위가 1부터 12까지이기 때문인데, 실제로 유효한 쌍이 만들어지는 경우는 다음과 같습니다.

• x = 6일 때: 유효한 쌍은 (2, 3) → f(6) = 1
• x = 10일 때: 유효한 쌍은 (2, 5) → f(10) = 1
• x = 12일 때: 유효한 쌍은 (3, 4) → f(12) = 1

따라서 전체 쌍의 개수는 총 3개입니다.

접근 방법

모든 x에 대해 일일이 쌍을 검사하는 완전 탐색은 매우 비효율적입니다. 대신 곱이 n 이하가 되는 (p, q) 쌍만 체계적으로 세는 것이 핵심입니다. 이 문제는 다음 단계로 해결할 수 있습니다.

• count를 0으로 초기화합니다.
• sqr을 n의 제곱근의 정수 부분에 1을 더한 값으로 설정합니다.
• base를 2부터 sqr - 1까지 반복합니다.
  • i를 1부터 min(base, ⌊n / base − base + 1⌋) 미만까지 반복합니다.
    • base와 i의 최대공약수(gcd)가 1이 아니면 다음 반복으로 건너뜁니다.
    • count에 ⌊(n − i × base) / (base × base)⌋ 값을 더합니다.
• count를 반환합니다.

여기서 gcd가 1인 경우만 세는 이유는, 두 수가 서로소일 때만 문제의 조건을 만족하기 때문입니다. 또한 탐색 범위를 제곱근까지만 한정함으로써 연산량을 크게 줄일 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해할 수 있습니다.

from math import sqrt, gcd

def solve(n):
   count = 0
   sqr = int(sqrt(n)) + 1
   for base in range(2, sqr):
      for i in range(1, min(base, n // base - base + 1)):
         if gcd(base, i) != 1:
            continue
         count += (n - i * base) // (base * base)

   return count

n = 12
print(solve(n))

입력

12

출력

3