AtCoder が提供しているABC（AtCoder Beginner Contest）383 D問題をC++とPythonで解いてみました。ABC383は、2024年12月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 9 Divisors（Difficulty : 884）
問題の詳細は、リンク先をご覧ください。
エラトステネスの篩を用いて素数表を作成し、条件を満たす整数を探索します。AtCoder Problems による Difficulty は 884 でした。
解答案
C++ プログラム例（ABC383D）
正の約数をちょうど 9 個持つ整数は、$p, q$ を素数とすると、$p^2 \times q^2$ の形か $p^8$ の形になります。9 を約数の積で $9 = 3 \times 3 = 1 \times 9$ の2通りしか表せないためです。
- $p^2 \times q^2$ の場合、約数は $1, p, p^2, q, p q, p^2 q, q^2, p q^2, p^2 q^2 $ の 9 個となります。
- $p^8$ の場合、約数は $1, p, p^2, … p^7, p^8$ の 9 個となります。
$N$ の制約が $1 \leqq N \leqq 4 \times 10^{12}$ であるため、余裕を持たせて、$2 \times 10^6$ までの素数表を作成します。素数表の作成には、エラトステネスの篩を使いました（6ー33行目）。
$N$ 以下の $p^2 \times q^2$ の形の整数を43～53行目で求めます。$p^8$ の形の整数を55～65行目で求めます
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define N 2000000
bool is_prime_table[N + 1];
vector<int> primes;
void generate_primes(int n)
{
is_prime_table[0] = false;
is_prime_table[1] = false;
for (int i = 2; i <= n; ++i) {
is_prime_table[i] = true;
}
for (int i = 2; i * i <= n; ++i) {
if (is_prime_table[i]) {
for (int j = i + i; j <= n; j += i) {
is_prime_table[j] = false;
}
}
}
for (int i = 2; i <= n; ++i) {
if (is_prime_table[i]) {
primes.push_back(i);
}
}
return;
}
int main()
{
ull n;
cin >> n;
generate_primes(N);
int result = 0;
for (int i = 0; i < (int)primes.size(); ++i) {
for (int j = i + 1; j < (int)primes.size(); ++j) {
ull p1 = primes[i];
ull p2 = primes[j];
if (p1 * p1 * p2 * p2 > n) {
break;
} else {
++result;
}
}
}
for (int i = 0; i < (int)primes.size(); ++i) {
ull t = primes[i];
t = t * t;
t = t * t;
t = t * t;
if (t > n) {
break;
} else {
++result;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC383D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 383 D"""
N = 2 * 10 ** 6
is_prime_rable = [True] * (N + 1)
primes = []
def generate_primes(n):
is_prime_rable[0] = False
is_prime_rable[1] = False
i = 2
while i * i <= n:
if is_prime_rable[i]:
for j in range(i + i, n + 1, i):
is_prime_rable[j] = False
i += 1
for i in range(2, n + 1):
if is_prime_rable[i]:
primes.append(i)
n = int(input())
generate_primes(N)
result = 0
for i in range(len(primes)):
for j in range(i + 1, len(primes)):
if primes[i] ** 2 * primes[j] ** 2 > n:
break
else:
result += 1
for i in range(len(primes)):
if primes[i] ** 8 > n:
break
else:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
高校数学で学んだ知識を活用しました。D問題をＣ問題より先に解きましたが、36分で解くことができました。自分にとってはよい結果です。
引き続き ABC の問題を紹介していきます。
