No.2782 Product of Mersenne Numbers
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もしくは右上の雲マークをクリックしてアカウントを作成してください。