はじめに

はじめまして！競技プログラミングをやっている高校生のButterflvです！

この度Qiitaのアカウントを作成したので自己紹介を少しと、初投稿の話題として先日開催された AtCoder Regular Contest 176 （Sponsored by Mynavi）のB問題である B - Simple Math 4 の公式解説と少し異なるアプローチを紹介します。

自己紹介

現在高校三年生です。「競技プログラミングをやっている」とは言っても僕の競技科学との出会いは数学オリンピック(JMO)で、きっかけは同級生の友人の勧めで OnlineMathContest という、数学のコンテストを定期的に開催しているサイトに参加し始めたことです。このサイトでコンテストを楽しみながら数学オリンピック風の問題に触れていき、JMO2024では本選に出場することができました。
（↓僕の OnlineMathContest のアカウント）

また、JMO予選の少し前に同じく友人に AtCoder Junior League に参加しないかと言われ AtCoder を始めたのが競技プログラミングとの出会いです。ただ、 Scratch を小学生のときによく触っていたのと、高校生になるくらいの時期に HTML, CSS, JavaScript を用いたWeb開発やCanvasでのゲーム作成をしていた経験もあり、プログラミング自体にはほとんど抵抗なく入ることができました。
AtCoderは現在茶色で、アカウントを一度作成し直しており、前のアカウントでは highest は1076でした。
（↓僕の AtCoder のアカウント）

一応競技科学の経歴として、科学の甲子園への出場も書いておきます。

AtCoder は AJL でかなりモチベがあるので頑張りたいです！！

もう一つ

Qiitaを始めたのは競技プログラミングやWeb開発の、主にフロントエンドの方で勉強したことや思ったことを書き残したいと思ったからです。よろしくお願いします。（バックエンドもできれば勉強したい...）

本題

今回は B - Simple Math 4 について。僕の解法を紹介させていただきたいと思います！（本質的には公式解説と同じ議論かもしれませんが...）

問題文

$2^N$ を $2^M-2^K$ で割ったあまりの $1$ の位を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 2\times 10^5$
$1\le N\le 10^{18}$
$1\le K\lt M \le 10^{18}$
$N,M,K$ は整数

まずは愚直に

前提として, $N,M,K,T$ の制約から $2^N,2^M,2^K$ を直接計算することはメモリの容量を考えると許されません. さらに, 余りを求める演算には桁数 $N$ に対して $O(N\ \mathrm{log}\ N)$ かかり, $2$ のべきの桁数が $N,M,K$ に比例することを考えると厳しいです. よってこの問題はあまりを $N,M,K$ を用いて $2$ のべきを含む形で表し, 最終的にそれを繰り返し二乗法を用いて $1$ テストケースあたり $O(\log(\mathrm{max}\{N,M,K\}))$ 解くものだろうと予想できます. これは十分高速で $T$ 個のテストケースに間に合います.

ひと工夫

$2^N$ を $2^M-2^K$ で割った商を $q$ あまりを $r$ とすると以下が成立します.
$$2^N=(2^M-2^K)\cdot q+r$$
このとき, 両辺が $2^K$ で割れそうだなとなります. そうすると以下のようになります.
$$2^{N-K}=\left(2^{M-K}-1 \right)\cdot q+\dfrac{r}{2^K}$$
このとき $N\ge K$ を仮定します. ($N\ge K$ が成立しないとき, 左辺が整数でなくなるため)
$$2^{N-K}-\left(2^{M-K}-1 \right)\cdot q=\dfrac{r}{2^K}$$
とすると, 左辺が整数であるので右辺は整数となります. よって整数 $N', M', r'$ でそれぞれ $N'=N-K,\ M'=M-K,\ r'=\dfrac{r}{2^K}$ のように置き換えることができ, 元の式は
$$2^{N'}=(2^{M'}-1 )\cdot q+r'$$ となります.

考察の本質部分

前節では $2^{N'}$ を $2^{M'}-1$ で割ったあまりの挙動を考える問題に帰着することができ, 文字の数が減ったので議論の対象がわかりやすくなりました.

ここでコードテストを取り出して $M'$ を固定しながら $N'$ を動かして実験するのもよいですが(コンテスト中僕はそうしました💦)一応数論的考察を入れておきます. 以下, 合同式の法を $2^{M'}-1$ とします. このとき, $2^{M'}-1\equiv 0\Longrightarrow 2^{M'}\equiv 1$ とでき, $k=1,2,3,\cdots ,M'-1 $ について $2^k$ は法 $2^{M'}-1$ を超えないため, $2$ のべきを $2^{M'}-1$ で割ったあまりの最も小さい周期は $M'$ であるとわかり, $2^{N'}\equiv 2^{N'\ \mathrm{mod}\ M'}$ とできます. これは法 $2^{M'}-1$ を超えないので結局 $r'=2^{N'\ \mathrm{mod}\ M'}$ とわかりました. 最終的に解答すべき値は $r$ の $1$ の位なので, 置き換えを戻すと $r=2^{(N-K)\ \mathrm{mod}\ (M-K)\ +K}$. この計算量は繰り返し二乗法などを用いるとざっくり $O(\log\log r)$ で十分高速です.

コーナーケースについて

上の考察には実はコーナーケースが存在します.

それは $M'=1$ のとき, つまり $M=K+1$ のときです. このとき,
$$2^M-2^K=2^{K+1}-2^K=2^K \ \Big| \ 2^N\ (\because N\ge K)$$ となってしまうため, あまりは $0$ になります.

場合分けの分けられたほうについて

前節の考察では $N\ge K$ を仮定して議論を進めたので $N\lt K$ の場合を考えます.

結論から言うと, この場合は $2^N$ が余りとなります. なぜなら, $2^M-2^K\ge 2^{K+1}-2^K = 2^K \gt 2^N\Longrightarrow 2^N\lt 2^M-2^K$ であるからです.

実装

以上で考察が完了したので実装をします. 以下に Python での実装を表示しています.

main.py

for _ in range(int(input())):
  N, M, K = map(int, input().split())
  if N >= K:
    if M == K+1: print(0)
    else: print(pow(2, (N-K)%(M-K) + K, 10))
  else:
    print(pow(2, N, 10))

おわりに

最終的な結果はもちろん公式解説と同じなのですが、公式解説は少し思いつきにくい質素な式変形だなと思ったのでなるべく簡単なルートで、コードテストの実験ベースでたどり着ける解法を紹介しました。(本問ではコーナーケースは証明を考えるよりコードテストで実験をするほうが気づきやすいと思います) AtCoder での数学問は、せっかくコンピューターの力を使えるということなので積極的に実験もしたいですね～

これからも Qiita で思ったことなどを投稿したいです。よろしくお願いします！！