No.3493 等比数列の和の素因数
p-adic
問題文最終更新日: 2026-04-03 19:32:11
yukicoder contest 496の他の問題:
問題文
入力に非負整数 $N$ と 素数 $P$ が与えられます。
$\sum_{i = 0}^{N} n^i$ が $P$ で割り切れるような正整数 $n$ が存在するか否かを判定してください。
入力
入力は次の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N,P$ が半角空白区切りで与えられます。
$N$ $P$
制約
入力は以下の制約を満たします：
- $N$ は $0 \leq N \leq 10^{18}$ を満たす整数
- $P$ は $2 \leq P \leq 10^{18}$ を満たす素数
出力
$\sum_{i = 0}^{N} n^i$ が $P$ で割り切れるような正整数 $n$ が存在する場合はYesと、存在しない場合はNoと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
0 2
出力
No
任意の正整数 $n$ に対し
$\displaystyle \sum_{i=0}^{N} n^i = \sum_{i=0}^{0} n^i = n^0 = 1 $
であり、これは $P = 2$ で割り切れません。
サンプル2
入力
1 3
出力
Yes
$n = 2$ の時
$\displaystyle \sum_{i=0}^{N} n^i = \sum_{i=0}^{1} 2^i = 2^0 + 2^1 = 3 $
であり、これは $P = 3$ で割り切れます。
サンプル3
入力
2 7
出力
Yes
$n = 2$ の時
$\displaystyle \sum_{i=0}^{N} n^i = \sum_{i=0}^{2} 2^i = 2^0 + 2^1 + 2^2 = 7 $
であり、これは $P = 7$ で割り切れます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。