No.3493 Prime Factors of the Sum of a Geometric Sequence
タグ : / 解いたユーザー数 20
作問者 : 👑
p-adic
Problem Statement
You are given a non-negative integer $N$ and a prime $P$ as input.
Determine whether there exists a positive integer $n$ such that $\sum_{i = 0}^{N} n^i$ is divisible by $P$.
Input
The input is given from standard input in $1$ line in the following format:
- On line $1$, $N,P$ are given, separated by a single space.
$N$ $P$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $0 \leq N \leq 10^{18}$
- $P$ is a prime satisfying $2 \leq P \leq 10^{18}$
Output
Print Yes if there exists a positive integer $n$ such that $\sum_{i = 0}^{N} n^i$ is divisible by $P$, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
0 2
Output
No
For any positive integer $n$, we have
$\displaystyle \sum_{i=0}^{N} n^i = \sum_{i=0}^{0} n^i = n^0 = 1 $
and this is not divisible by $P = 2$.
Sample 2
Input
1 3
Output
Yes
When $n = 2$, we have
$\displaystyle \sum_{i=0}^{N} n^i = \sum_{i=0}^{1} 2^i = 2^0 + 2^1 = 3 $
and this is divisible by $P = 3$.
Sample 3
Input
2 7
Output
Yes
When $n = 2$, we have
$\displaystyle \sum_{i=0}^{N} n^i = \sum_{i=0}^{2} 2^i = 2^0 + 2^1 + 2^2 = 7 $
and this is divisible by $P = 7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。