← 返回比赛
已结束 GESP巅峰赛#27
← 上一题 下一题 →

A5729 | Alice 的数学构造

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定正整数 $n$ 。设 $a$ 为 $\{1,2,\dots,n\}$ 的一个排列。定义前缀乘积序列
$$ b_1\equiv a_1\pmod n,\quad b_i\equiv b_{i-1}\cdot a_i\pmod n\ (2\le i\le n). $$
若 $b$ 恰好是 $\{0,1,\dots,n-1\}$ 的一个排列（每个余数出现且只出现一次），称该 $a$ 为可行。本题仅需判断是否存在可行排列。

输入格式

- 第一行一个整数 $T$
- 接下来 $T$ 行，每行一个整数 $n$ 。

输出格式

对每组数据输出一行：存在则输出 YES，否则输出 NO。

输入输出样例

输入 #1
5 
10
9
7
3
2
输出 #1
NO
NO
YES
YES
YES
输入 #2
5
3
2
9
11
15
输出 #2
YES
YES
NO
YES
NO
C++ 编辑器
输入
输出