No.3233 Permutation Check
p-adic
YY-otterNote
The execution time limit for this problem is 1000[ms].
Problem Statement
You are given $2$ positive integers $N, M$ as input.
Determine whether the integer sequence $A$ of length $N$, uniquely characterized by the following condition, is a permutation.
- For any positive integer $i$ not exceeding $N$, the $i$-th component of $A$ is the remainder when $i^M$ is divided by $N$.
Here, $A$ being a permutation means that the components of $A$ are pairwise distinct.
Input
The input is given from standard input in $1$ line in the following format:
- On line $1$, $N, M$ are given, separated by a half-width space.
$N$ $M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$.
- $M$ is an integer satisfying $1 \leq M \leq 10^2$.
Output
Print Yes if $A$ is a permutation, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
1 1
Output
Yes
We have $A = (1^M \bmod N) = (1^1 \bmod 1) = (0)$, and $A$ has only $1$ component. In particular, $A$ is a permutation.
Sample 2
Input
2 1
Output
Yes
We have $A = (1^M \bmod N, 2^M \bmod N) = (1^1 \bmod 2, 2^1 \bmod 2) = (1,0)$, and the components of $A$ are pairwise distinct. That is, $A$ is a permutation.
Sample 3
Input
3 2
Output
No
We have $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)$, and component number $1$ and component number $2$ of $A$ coincide, both being $1$. That is, $A$ is not a permutation.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。