으아니! 리매치라니!
헐 9시 30분이라니!
뭐, 전 리매치해도 하위권 근처에서 노는 사람인걸요. 리매치하더라도 이미 붙은 12명 / 티셔츠 50명은 그냥 붙은 걸로 / 티셔츠 주는 걸로 하고, 또 하면 안 되나요? 티셔츠라도 받게...

아무튼 이거 어렵군요.

0 단계

발로 짠 small 전용 코드. Small은 쉽습니다.

#!/usr/bin/env python3.2

import sys
import os
import math

n_max = 1000000
nb = [0 for i in range(0, n_max + 1)]
gg = [0 for i in range(0, n_max + 1)]
hh = [[] for i in range(0, n_max + 1)]
for i in range(2, n_max+1):
  r = 0
  for j in range(2,int(math.sqrt(i))+1):
    if i % j == 0:
      r += 2
      if j * j == i:
        r -= 1
      if gg[i] == 0:
        gg[i] = j
  nb[i] = r
for j in range(2, n_max+1):
  x = nb[j]
  hh[x].append(j)

cases = sys.stdin.readlines()
for case in range(1, len(cases)):
  ans = 0
  data = cases[case].split()
  N = int(data[0])
  M = int(data[1])
  x = nb[N]
  for i in hh[x]:
    if i < N:
      if gg[i] >= M:
        ans = ans + 1
    else:
      break
  print("Case #{}: {}".format(case, ans))

1 단계

문제를 잘 해석하면 다음 조건을 만족하는 x의 수를 구하는 겁니다.

• 2 <= x < N
• x의 약수의 수 = N의 약수의 수
• M <= x의 가장 작은 소인수

2단계

10^9 이하의 모든 소수를 계산해서 array나 그 비슷한 형태로 가지고 있습니다. 제약 조건이 다음과 같은데요.

• 2 <= M <= N (1)
• 2 <= N <= 10^17 (2)
• N <= M * 10^9 (3)

여기서 eq.3을 다르게 보면 N / M <= 10^9이 됩니다. M이 x의 가장 작은 소인수의 lower bound이므로, N/M은 x의 가장 큰 소인수의 upper bound가 되겠죠. 그래서 10^9보다 더 큰 소수는 필요 없어요.

그리고 M의 존재는 "소수인 번호끼리 자매인가요?"같은 고민을 덜어주네요. N이 소수이면 답은 그냥 0입니다. 자기 자신이 막내 동생이 되는 것은 아니므로 소수에 대해서는 자기 자신을 제외한 가장 작은 소인수가 정의 되지 않으니까요. (엄밀하게 하려면 문제에서 설명을 해줘야 됐을 것 같군요.)

3단계

함수 foo(N, M, D)를 다음과 같이 정의합니다.

• N: 조건을 만족하는 x의 upper bound (inclusive)
• M: x의 가장 작은 소인수의 lower bound (inclusive)
• D: 1과 자기 자신을 포함한 약수의 개수 1과 자기 자신을 포함하는 이유는 그게 계산이 편하니까요. x = 2^p 3^q 5^r ...이면 약수의 수가 (p+1)(q+1)(r+1)...이 되는 건 알고 계시죠?

그러면 foo(100, 2, 9)같은 건 9 = 1 * 9에서 2^8이 벌써 100을 넘으니까 집어 치우고, 9 = 3 * 3에서 x= a^2 b^2형태를 찾아야 되는데,

• 2^2 * ? 인 경우의 수: foo(100/4, 3, 3)

가 되겠죠.

Recursion을 적절히 활용해서 풀면 됩니다. 슈도 코드는 다음과 같아요. 핵심만 나타내려고 자잘한 조건은 지웠어요.

mi는 몇 번째 소수인지를 나타냅니다. prime_list는 소수 목록이고, pow_table은 단순 무식하게 모든 소수의 거듭제곱을 넣어둔 table이에요.

lli foo(const lli N, const int mi, const int D)
{
  if (N == 0)
    return 0ll;
  if (D == 1)
    return 1ll;
  lli r = 0;
  int imax = D;
  for (int i = 1; (i + 1) <= imax; ++i) {
    if (D % (i + 1))
      continue;
    lli N2 = N / pow_table[mi][i];
    if (!N2)
      break;
    int D2 = D / (i + 1);
    if (D2 > 1 && N2 < prime_list[mi + 1])
      break;
    r += foo(N2, mi + 1, D2);
  }
  r += foo(N, mi + 1, D); // skip prime_list[mi]
  return r;

4단계

너무 단순하게 짜면 오래 걸릴 수도 있는데, 적절히 최적화를 해주면 됩니다. (이게 가장 어려웠어요.)

처음에 짠 게 너무 너무 너무 너무 오래 걸렸는데, 어디가 병목인지 분석이 잘 안 되어서 이것저것 고치다 보니, 뭐가 필요한 최적화이고 뭐가 불필요한 최적화인지 저도 몰라요. 고치다 보니 갑자기 답이 나오게 되었네요.