AtCoder

ABC284 D問題(Happy New Year 2023)を解く

AtCoder_ABC284_D

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 でした。ABC D問題として、標準的な問題です。

解答案

実行時間制限が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のような大きな差ではありませんでした。問題作成する方も、多くの人が楽しめるように工夫されているのだと思います。

ABC284 について、引き続き、E問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA