問題一覧 > 教育的問題

No.2782 メルセンヌ数総乗

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 : 👑 p-adic / テスター : Taka
1 ProblemId : 10725 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-11 12:07:07

問題文

22 以上の各整数 nn に対し Mn=2n−1M_n = 2^n - 1 と定めます。

正整数 NN が与えられます。

∏n=2NMn\prod_{n=2}^{N} M_n が MN+1M_{N+1} で割り切れるか否かを判定してください。

総乗の記号 ∏\prod を知らない人向けの説明はこちらです。（クリックで開く）

　

正整数 kk に対し ∏n=2kMn\prod_{n=2}^{k} M_n は次の式で再帰的に定義されます：

∏n=2kMn={1(k=1)Mk∏n=2k−1Mn(k>1)\displaystyle \prod_{n=2}^{k} M_n = \left\{ \begin{array}{ll} 1 & (k = 1) \\ M_k \prod_{n=2}^{k-1} M_n & (k > 1) \end{array} \right.

例えば kk が小さい場合の値は次のように計算できます。

∏n=21Mn=1∏n=22Mn=M2∏n=21Mn=M2×1=M2∏n=23Mn=M3∏n=22Mn=M3M2∏n=24Mn=M4∏n=23Mn=M4M3M2\displaystyle \begin{array}{rcl} \displaystyle \prod_{n=2}^{1} M_n &\displaystyle = &\displaystyle 1 \\ \displaystyle \prod_{n=2}^{2} M_n &\displaystyle = &\displaystyle M_2 \prod_{n=2}^{1} M_n = M_2 \times 1 = M_2 \\ \displaystyle \prod_{n=2}^{3} M_n &\displaystyle = &\displaystyle M_3 \prod_{n=2}^{2} M_n = M_3 M_2 \\ \displaystyle \prod_{n=2}^{4} M_n &\displaystyle = &\displaystyle M_4 \prod_{n=2}^{3} M_n = M_4 M_3 M_2 \end{array}

要するに総乗は数列を順に掛け合わせたものです。

入力

入力は以下の形式で標準入力から 11 行で与えられます：

  • 11 行目に NN が与えられます。
NN

制約

入力は以下の制約を満たします：

  • NN は 1≤N≤311 \leq N \leq 31 を満たす整数である。

出力

∏n=2NMn\prod_{n=2}^{N} M_n が MN+1M_{N+1} で割り切れる場合はYesと出力し、そうでない場合はNoと出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1
出力
No

∏n=2NMn=∏n=21Mn=1MN+1=22−1=3\displaystyle \begin{array}{rcl} \displaystyle \prod_{n=2}^{N} M_n &\displaystyle = &\displaystyle \prod_{n=2}^{1} M_n = 1 \\ & & \\ \displaystyle M_{N+1} &\displaystyle = &\displaystyle 2^2 - 1 = 3 \end{array}

です。11 は 33 で割り切れないのでNoと出力します。

サンプル2
入力
2
出力
No

∏n=2NMn=∏n=22Mn=M2=3MN+1=23−1=7\displaystyle \begin{array}{rcl} \displaystyle \prod_{n=2}^{N} M_n &\displaystyle = &\displaystyle \prod_{n=2}^{2} M_n = M_2 = 3 \\ & & \\ \displaystyle M_{N+1} &\displaystyle = &\displaystyle 2^3 - 1 = 7 \end{array}

です。33 は 77 で割り切れないのでNoと出力します。

サンプル3
入力
5
出力
Yes

∏n=2NMn=∏n=25Mn=M5M4M3M2=31×15×7×3=9765MN+1=26−1=63\displaystyle \begin{array}{rcl} \displaystyle \prod_{n=2}^{N} M_n &\displaystyle = &\displaystyle \prod_{n=2}^{5} M_n = M_5 M_4 M_3 M_2 = 31 \times 15 \times 7 \times 3 = 9765 \\ & & \\ \displaystyle M_{N+1} &\displaystyle = &\displaystyle 2^6 - 1 = 63 \end{array}

です。97659765 は 6363 で割り切れるのでYesと出力します。

サンプル4
入力
31
出力
No

∏n=2NMn=∏n=231Mn=M31⋯M3M2=59082264910556218588927381962395959089984146823674634884348598265548922511678684778107833428139502347122884103295800680569054115129568844774601953125MN+1=232−1=4294967295\displaystyle \begin{array}{rcl} \displaystyle \prod_{n=2}^{N} M_n &\displaystyle = &\displaystyle \prod_{n=2}^{31} M_n = M_{31} \cdots M_3 M_2 = 59082264910556218588927381962395959089984146823674634884348598265548922511678684778107833428139502347122884103295800680569054115129568844774601953125 \\ & & \\ \displaystyle M_{N+1} &\displaystyle = &\displaystyle 2^{32} - 1 = 4294967295 \end{array}

です。5908226491055621858892738196239595908998414682367463488434859826554892251167868477810783342813950234712288410329580068056905411512956884477460195312559082264910556218588927381962395959089984146823674634884348598265548922511678684778107833428139502347122884103295800680569054115129568844774601953125 は 42949672954294967295 で割り切れないのでNoと出力します。

このように64bit整数の範疇に収まらないこともあることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。