ABC284 D問題（Happy New Year 2023）を解く

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秒です。演算ができる回数は、多くても 10⁹ 回程度と考えられています。素因数分解する $N$ の制約は、以下となっています。

$$1\leqq N\leqq 9\times {10}^{18}$$

$N$ が素数の場合、$\sqrt{N}$ までの数で割る必要があるため、間に合わないような気がします。ただし、$N=p^{2}q$（$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 の問題を紹介していきます。