ABC 400のC問題 2^a b^2

2025-04-10

AtCoder の ABC 400 の C 問題にコンテスト終了後チャレンジしてみた。数学は苦手だけど、a を偶数と奇数の場合分けして考えたら予想外の簡単な計算で答えを求めることが出来た。

コンテスト終了後に C 問題にチャレンジしてみました。こおいう数学の問題は苦手です。

問題

整数 N が与えられて、次の数式を満たす N までの「良い整数」の数を答える問題。

$$ N = 2^a \times b^2 $$

a と b の最大値は、それぞれ $$ log_2 N = \frac{log N} {log 2} $$と$$ \sqrt{\frac{N}{2}} $$になります。そこで a と b をスキャンすることを考えたのですが、競技プログラミングの問題なのでもっと良い方法があるはずです。

式の形がきれいなので、式を変形すると「良い整数」を作る法則が見つかるような気がしました。

そこで a が偶数と奇数の場合を考えて$$ a = 2x$$ $$ a = 2y +1 $$として式を変形しました。

$$ N = 2^{2x} \times b^2 = (2^x \times b)^2 $$

$$ \sqrt{N} = 2^xb $$

$$ \frac{\sqrt{N}}{2^x} = b $$

b が整数ということは、$$\sqrt{N}$$も整数である必要があります。よって N は、1, 4, 9, 16 といった何かの二乗で表せる数である必要がああります。

同時に 2^x (ただし x > 0)で割った結果も整数である必要があります。この時に x の範囲を考える必要がありますが、条件が成り立つ x がいくつの場合でも常に 2 の倍数なので同時に x=1 の時も条件が成立するはずです。そのため √N は偶数である必要があります¹。

同様に考えて √N が偶数ならば、N も偶数である必要があります。さらに二乗して N となる何かの数自体も偶数である必要があります。

よって a が偶数の場合に「良い整数」N を作る何かの数は、1… √N の内の偶数が答えとなります。そして偶数なので個数は

$$ \frac{\sqrt{N}}{2}$$

となります。

偶数の場合と同じように式を整理して、b が整数という条件を満たす N を探します。

$$ N = 2^{2y+1} \times b^2 = 2^{2y} \times 2 \times b^2 $$

$$ \frac{N}{2} = (2^y \times b)^2 $$

$$ \sqrt{\frac{N}{2}} = 2^yb $$

$$ \frac{\sqrt{\frac{N}{2}}}{2^y} = b $$

ここで y は 0 も含むため 2^y は 1 を取ることが出来ます。そのため a が偶数のときと異なり

$$ \sqrt{\frac{N}{2}} = b $$

を満たせば良くなります。

よって「良い整数」N を作る何かの数は、1… √(N/2) となります。今回は偶数の場合と異なり 2 で割る必要がないため、全ての何かの数を二乗した整数を N と出来ます。よって個数は、√(N/2)の整数部分となります。

求める平方根などは実数ではなく整数なので、sqrt()の代わりにisqrt()を、/の代わりに//を使用しました。

import math

n = int(input())

count = math.isqrt(n//2) + math.isqrt(n) // 2

print(count)

a を偶数と奇数に分けたので、「良い整数」の重複を探すためにスキャンが必要だと考えていましたが、与えられた N を式に代入するだけで条件を満たす整数の数が分かってしまい驚きました。