Pythonでa、b、cのいずれかで割り切れる数列のn番目の項を求めるプログラム

問題概要

4つの整数 n、a、b、c が与えられます。a、b、c のいずれかで割り切れる正の整数を小さい順に並べた数列の中から、n番目(0始まりインデックス)の項を求める必要があります。

たとえば、入力が n = 8、a = 3、b = 7、c = 9 の場合、出力は 18 となります。これは、条件を満たす数列の最初の9項が [1, 3, 6, 7, 9, 12, 14, 15, 18] となり、0始まりで数えると8番目の項が18であるためです。

アプローチ

この問題は二分探索と包除原理を組み合わせることで効率的に解けます。ある値 x 以下に存在する、a・b・c のいずれかで割り切れる数の個数は、包除原理を使って次のように計算できます。

個数 = ⌊x/a⌋ + ⌊x/b⌋ + ⌊x/c⌋ − ⌊x/lcm(a,b)⌋ − ⌊x/lcm(b,c)⌋ − ⌊x/lcm(a,c)⌋ + ⌊x/lcm(a,b,c)⌋

ここで lcm は最小公倍数を表します。この個数が n 以上になる最小の x を二分探索で求めれば、それが答えになります。

解決手順

• a、b、c の最小値が 1 の場合、すべての正の整数が条件を満たすため、そのまま n を返します。
• ab := lcm(a, b)、bc := lcm(b, c)、ca := lcm(a, c) を計算します。
• abc := lcm(ab, c) を計算します。
• 探索範囲を left := 1、right := 10^9 に設定します。
• left ≤ right である限り、以下を繰り返します。
  • mid := (left + right) // 2 とします。
  • na := mid ÷ a の商、nb := mid ÷ b の商、nc := mid ÷ c の商を求めます。
  • nab := mid ÷ ab の商、nbc := mid ÷ bc の商、nca := mid ÷ ca の商を求めます。
  • nabc := mid ÷ abc の商を求めます。
  • numterms := na + nb + nc − nab − nbc − nca + nabc を計算します。
  • numterms > n の場合:right := mid − 1 として探索範囲を左半分に狭めます。
  • numterms < n の場合:left := mid + 1 として探索範囲を右半分に狭めます。
  • それ以外の場合:mid − min(mid mod a, mid mod b, mid mod c) を返します。これにより、mid が実際に a・b・c のいずれかで割り切れる値へと調整されます。
• ループが終了しても答えが見つからない場合は -1 を返します。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

import math
def lcm(a, b):
   return (a * b) // math.gcd(a, b)
class Solution:
   def solve(self, n, a, b, c):
      if min(a, b, c) == 1:
         return n
      ab, bc, ca = lcm(a, b), lcm(b, c), lcm(a, c)
      abc = lcm(ab, c)
      left, right = 1, 10 ** 9
      while left <= right:
         mid = (left + right) // 2
         na = mid // a
         nb = mid // b
         nc = mid // c
         nab = mid // ab
         nbc = mid // bc
         nca = mid // ca
         nabc = mid // abc
         numterms = na + nb + nc - nab - nbc - nca + nabc
         if numterms > n:
            right = mid - 1
         elif numterms < n:
            left = mid + 1
         else:
            return mid - min(mid % a, mid % b, mid % c)
      return -1
ob = Solution()
n = 8
a = 3
b = 7
c = 9
print(ob.solve(n, a, b, c))

入力

8, 3, 7, 9

出力

18

まとめ

このアルゴリズムのポイントは、二分探索によって候補値を絞り込みながら、包除原理を使えば各候補値以下に含まれる条件適合の項数を定数時間で計算できる点です。単純に数列を1つずつ生成していく方法では n が大きい場合に非現実的な計算量となりますが、この手法なら計算量はおおよそ O(log(10^9)) 程度に抑えられ、大きな入力に対しても高速に動作します。