Pythonで約数の約数の個数の総和を求めるプログラム

問題の概要

2つの整数 m と a が与えられたとします。このとき、次のように定義される数 n を考えます。

n = p₁^(a+1) × p₂^(a+2) × … × p_m^(a+m)

ここで、p_i は i 番目の素数(i > 0)を表します。求めたいのは、n のすべての約数 x に対する f(x) の値の合計 k です。f(x) は「x の約数の個数」を返す関数です。

具体例で確認する

入力が m = 2、a = 1 の場合を考えてみましょう。このときの出力は 60 になります。

• n = 2² × 3³
• n = 4 × 27
• n = 108

108 の約数は、1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108 の12個です。

各約数に対する f(x) の値をすべて足し合わせると、次のようになります。

f(1) + f(2) + f(3) + f(4) + f(6) + f(9) + f(12) + f(18) + f(27) + f(36) + f(54) + f(108)
= 1 + 2 + 2 + 4 + 4 + 3 + 5 + 6 + 4 + 9 + 8 + 12
= 60

解法の考え方

n = ∏ p_i^e_i と素因数分解できるとき、n の各約数 d についてその約数の個数 τ(d) を合計した値は、素因数ごとに独立して計算できます。具体的には、指数 e に対して 1 + 2 + … + (e+1) = (e+1)(e+2)/2 を各素因数について掛け合わせたものが答えになります。

本問題では指数が e_i = a + i となるため、答えは次の式で表せます。

k = ∏_i=1..m (a+i+1)(a+i+2)/2

この積を効率よく求めるため、あらかじめ summ(n) = n(n+1)/2 の累積積リストを作成し、大きな数の除算はモジュロ逆数を利用して処理します。

アルゴリズムの手順

• MOD := 10⁹ + 7 とする。
• 関数 summ(n) を定義する:((n × (n + 1)) / 2) の床関数値を返す。
• 関数 division(a, b, mod) を定義する:a ÷ b の結果を mod で割った余りを返す。
  • a mod b = 0 の場合は、a / b の床関数値をそのまま返す。
  • それ以外の場合は、a := a + mod × division((-a) mod b, mod mod b, b) としてから、(a / b) mod mod を返す。
• mat := [1] というリストを用意する。
• mat の長さが m + a 以下である間、mat の末尾に (mat[-1] × summ(len(mat)+1)) mod MOD を追加していく。
• division(mat[m + a], mat[a], MOD) を返す。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

MOD = 10**9 + 7

def summ(n):
    return ((n) * (n + 1)) // 2

def division(a, b, mod):
    if a % b == 0:
        return a // b
    a += mod * division((-a) % b, mod % b, b)
    return (a // b) % mod

def solve(m, a):
    mat = [1]
    while len(mat) <= m + a:
        mat.append((mat[-1] * summ(len(mat)+1)) % MOD)
    return division(mat[m + a] , mat[a], MOD)

print(solve(2, 1))

実行結果

入力:

2, 1

出力:

60

まとめ

この記事では、n = p₁^(a+1) × … × p_m^(a+m) で表される数 n の各約数について、さらにその約数の個数を合計する問題を扱いました。答えは各素因数の指数から (e+1)(e+2)/2 を掛け合わせる形で閉形式で求められるため、累積積とモジュロ逆数を組み合わせれば、大きな m や a に対しても高速に計算できます。競技プログラミングで頻出の「約数個数関数の和」と「mod 下的除算」のテクニックを同時に学べる良い例題といえるでしょう。