AtCoder が提供しているABC（AtCoder Beginner Contest）284 のD問題をC++とPythonで解いてみました。ABC284は、2023年1月7日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Happy New Year 2023（Difficulty : 658）
問題はリンク先をご覧ください。
ABC284 D問題 Happy New Year 2023
与えられた数字を素因数分解しますが、一工夫が必要な問題です。AtCoder Problems による Difficulty は、658 でした。
解答案
実行時間制限が3秒です。演算ができる回数は、多くても 109 回程度と考えられています。素因数分解する $N$ の制約は、以下となっています。
$$ 1\leqq N \leqq 9 \times 10^{18}$$
$N$ が素数の場合、$\sqrt{N}$ までの数で割る必要があるため、間に合わないような気がします。ただし、$N = p^2q$（$p$、$q$ は素数）という条件が付いています。このため、$p$、$q$ のどちらかは、$\sqrt[3]{N} = \sqrt[3]{9} \times 10^6 \doteqdot 2.08 \times 10^6$ 以下となります。一番小さい約数を求めることは、時間的に間に合います。
$N$ の約数がひとつ見つかったとします。問題の制約からこれは素数となります。この値を $a$ とします。このとき、以下の方法で、$p$、$q$ を求めることができます。
- $(N / a)$ が、もう一度 $a$ で割り切れる。この場合、$p = a$、$q = N / a^2$ となる。
- $(N / a)$ が、$a$ で割り切れない。この場合、$p = \sqrt{N / a}$、$q = a$ となる。
もし、$a$ が見つかった後に、残りの約数を割りながら確認すると、時間的に間に合いません。
C++ プログラム例（ABC284D）
上記の考察をそのままプログラムに落とし込みました。使う整数の型は、unsinged long long としました。
$p = \sqrt{N / a}$ を求めるために sqrt 関数を使っていますが、浮動小数点数の誤差があるため、0.5 を加えて、（整数化して）切り捨てしています。
補足すると、double の精度は、53ビットで10進数換算で約15桁となります。$N / a$ の最大値は、$a = 2$ の場合の $4.5 \times 10^{18}$ となり、一時的に精度が足りなくなります。ただし、$\sqrt{N / a}$ が $\sqrt{4.5} \times 10^9$ となるため、四捨五入すれば、足りない精度が結果に影響を及ぼさないことが分かります。
以下が、C++ のプログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
ull n;
cin >> n;
ull p, q;
for (ull j = 2; j < n; ++j) {
if (n % j == 0) {
n /= j;
if (n % j == 0) {
p = j;
q = n / j;
} else {
p = (ull)(sqrt((double)n) + 0.5);
q = j;
}
break;
}
}
cout << p << " " << q << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC284D）
Python 版も、考察した式をそのままプログラムにしました。
"""AtCoder Beginner Contest 284 D"""
import math
t = int(input())
for i in range(t):
n = int(input())
for j in range(2, n):
if n % j == 0:
n //= j
if n % j == 0:
p = j
q = n // j
else:
p = int(math.sqrt(n) + 0.5)
q = j
break
print(p, q)こちらも「AC」と判定されました。
最後に
素因数分解の問題ですが、問題の制約から、ひとつ約数を見つければ、残りが分かるという構造になっていました。
ABC284 は、C問題（Difficulty 193）とD問題（Difficulty 658）に難易度の差があります。ただし、ABC281、ABC282のような大きな差ではありませんでした。問題作成する方も、多くの人が楽しめるように工夫されているのだと思います。
引き続き ABC の問題を紹介していきます。
