問題一覧 > 教育的問題

No.2782 Product of Mersenne Numbers

レベル : / AI推定難易度 : 243 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 113
作問者 : 👑 p-adic / テスター : Taka
お気に入りにしたユーザー ProblemId : 10725 / 自分の提出
問題文最終更新日: 2024-03-11 12:07:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 433 (順位表) の他の問題:

Problem Statement

For each integer $n$ greater than or equal to $2$, define $M_n = 2^n - 1$.

You are given a positive integer $N$.

Determine whether $\prod_{n=2}^{N} M_n$ is divisible by $M_{N+1}$.

Here is an explanation for those unfamiliar with the product symbol $\prod$. (Click to open)

 

For a positive integer $k$, $\prod_{n=2}^{k} M_n$ is defined recursively by the following formula:

$\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. $

For example, the values for small $k$ can be computed as follows.

$\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} $

In short, the product is the result of multiplying the terms of a sequence in order.

Input

The input is given from standard input in $1$ line in the following format:

  • $N$ is given on line $1$.
$N$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 31$.

Output

Print Yes if $\prod_{n=2}^{N} M_n$ is divisible by $M_{N+1}$, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
1
Output
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} $

Since $1$ is not divisible by $3$, print No.

Sample 2
Input
2
Output
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} $

Since $3$ is not divisible by $7$, print No.

Sample 3
Input
5
Output
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} $

Since $9765$ is divisible by $63$, print Yes.

Sample 4
Input
31
Output
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} $

Since $59082264910556218588927381962395959089984146823674634884348598265548922511678684778107833428139502347122884103295800680569054115129568844774601953125$ is not divisible by $4294967295$, print No.

Note that, as in this case, values may not fit within the range of a 64-bit integer.

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