問題一覧 > 教育的問題

No.3233 順列判定

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 : 👑 p-adic / テスター : YY-otter
ProblemId : 10680 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-02 16:21:04

注意

この問題の実行時間制限は1000[ms]です。

問題文

入力に $2$ 個の正整数 $N, M$ が与えられます。

　

次の条件で一意に特徴づけられる長さ $N$ の整数列 $A$ が順列であるか否かを判定してください。

  • $N$ 以下の任意の正整数 $i$ に対し、$A$ の $i$ 個目の成分は $i^M$ を $N$ で割った余りである。

ここで $A$ が順列であるとは、$A$ の各成分が互いに相異なるということです。

入力

入力は以下の形式で標準入力から $1$ 行で与えられます：

  • $1$ 行目に $N, M$ が半角空白区切りで与えられます。
$N$ $M$

制約

入力は以下の制約を満たします：

  • $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
  • $M$ は $1 \leq M \leq 10^2$ を満たす整数である。

出力

$A$ が順列である場合はYesと出力し、そうでない場合はNoと出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1 1
出力
Yes

$A = (1^M \bmod N) = (1^1 \bmod 1) = (0)$ であり、$A$ は $1$ つしか成分を持ちません。特に $A$ は順列です。

サンプル2
入力
2 1
出力
Yes

$A = (1^M \bmod N, 2^M \bmod N) = (1^1 \bmod 2, 2^1 \bmod 2) = (1,0)$ であり、$A$ は各成分が互いに相異なります。すなわち $A$ は順列です。

サンプル3
入力
3 2
出力
No

$A = (1^M \bmod N, 2^M \bmod N, 3^M \bmod N) = (1^2 \bmod 3, 2^2 \bmod 3, 3^2 \bmod 3) = (1,1,0)$ であり、$A$ は $1$ 個目の成分と $2$ 個目の成分が共に $1$ で一致しています。すなわち $A$ は順列ではありません。

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