ABC383 D問題の解説（Python）

はじめに

こんにちは。てくますプロジェクトのYukkinです！　この記事では、ABC383のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

本記事は、数学・情報・論理パズルを楽しむ Techmath Project Advent Calendar 2024 の9日目の記事でもあります。アドベントカレンダーの応援や購読をしていただけると嬉しいです。

ABC383　D – 9 Divisors

問題

問題

\(N\) 以下の正の整数のうち、正の約数をちょうど 9 個持つものの個数を求めてください。

制約

• \(1 \leqq N \leqq 4×10^{12}\)

思考の筋道

正の約数の個数の求め方

整数の正の約数の個数は、素因数分解を行い、各素因数の指数（右肩の数字）に着目することで求めることができます。

このように、各指数に1を加えてそれらの積を計算することで、正の約数の個数を求められます。この方法は整数分野の知識として、覚えておくとよいでしょう。

本題

さて、今回の問題では、正の約数の個数が 9 個と分かっています。これに該当する素因数分解の形を考えましょう。

正の約数の個数が9個になる条件は、9を1つ以上の正の整数の積で表す方法に対応します。具体的には次の2通りです。

• 9
  素数 \(p\) を用いて、\(p^8\) と素因数分解できるパターン
• 3×3
  素数 \(p, q\) を用いて、\(p^2×q^2\) と素因数分解できるパターン

このように書き表せる整数の個数を数えていきましょう。

ここで、前者はともかく、後者はTLE（実行時間超過）の心配があるので、確認します。

まず、\(p<q\) とします。

\(4×10^{12} \geqq p^2×q^2 > p^2×p^2 \) から、 \(p\) の値は1500程度まで調べれば十分であると分かります。

一方、\(q\) は最大で \(10^6\) 程度まで調べる必要があります。

ただし、\(p\) の値が少し大きくなると、それに伴い \(q\) を調べる範囲は大幅に減少します。

そのため、全体としては計算量が増えすぎず、TLE（実行時間超過）にはならないと見込まれます。

コード

# エラトステネスのふるいで素数を列挙する
def eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        if i * i > n:
            break
        if not is_prime[i]:
            continue
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [p for p in range(n + 1) if is_prime[p]]
    return prime_numbers


N = int(input())

primes = eratosthenes(int(N**0.5) + 1)
count = 0

for p in primes:
    if p**8 > N:
        break
    count += 1

for i in range(len(primes)):
    for j in range(i + 1, len(primes)):
        if primes[i] ** 2 * primes[j] ** 2 > N:
            break
        count += 1

print(count)

以上、ABC383のD問題の解説でした！

では、またね。

リンク