No.2782 メルセンヌ数総乗
タグ : / 解いたユーザー数 107
作問者 : 👑
p-adic
/ テスター :
Taka
問題文
$2$ 以上の各整数 $n$ に対し $M_n = 2^n - 1$ と定めます。
正整数 $N$ が与えられます。
$\prod_{n=2}^{N} M_n$ が $M_{N+1}$ で割り切れるか否かを判定してください。
総乗の記号 $\prod$ を知らない人向けの説明はこちらです。（クリックで開く）
正整数 $k$ に対し $\prod_{n=2}^{k} M_n$ は次の式で再帰的に定義されます：
$\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. $
例えば $k$ が小さい場合の値は次のように計算できます。
$\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} $
要するに総乗は数列を順に掛け合わせたものです。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N$ が与えられます。
$N$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 31$ を満たす整数である。
出力
$\prod_{n=2}^{N} M_n$ が $M_{N+1}$ で割り切れる場合はYesと出力し、そうでない場合はNoと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1
出力
No
$\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} $
です。$1$ は $3$ で割り切れないのでNoと出力します。
サンプル2
入力
2
出力
No
$\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} $
です。$3$ は $7$ で割り切れないのでNoと出力します。
サンプル3
入力
5
出力
Yes
$\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} $
です。$9765$ は $63$ で割り切れるのでYesと出力します。
サンプル4
入力
31
出力
No
$\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} $
です。$59082264910556218588927381962395959089984146823674634884348598265548922511678684778107833428139502347122884103295800680569054115129568844774601953125$ は $4294967295$ で割り切れないのでNoと出力します。
このように64bit整数の範疇に収まらないこともあることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。