ARC118D
sim_sugar
·
2023-01-31 16:42:37
·
个人记录
考虑所有数可以被表示成 a^ib^j ，我们首先找到 a 模 p 的阶 n ，S = \{a^i|i \in [0,n)\} ，然后找到最小的 m \gt 0 使得 b^m \in S ，那么原问题可以转化为一个 n \times m 的网格，每次可以四个方向走，最后一行向下走会走回第一行的这一列，最后一列向右走会走到奇怪的某一行的第一列。
先特判掉无解（n \times m \ne p-1 ）和 n=1 或 m=1 的情况。
这个奇怪的行看起来就很奇怪所以我们构造一种不需要从最后一列向右走的方案：
$2 \nmid n$ 时，考虑交换 $a,b$，因为 $a,b$ 中一定有至少一个数的阶是偶数（如果两个的阶都是奇数且 $p \ne 2$，考虑原根 $g$ 那么 $a=g^A,b=g^B$ 满足 $A,B$ 都是偶数，因为 $n = \dfrac{p-1}{A},m = \dfrac{p-1}{B}$ 都是奇数，那么一个 $x=g^X$ 能被表示出来必须满足 $2 \mid x$，$a^ib^j$ 就不能表示所有的 $x$。），所以转化为了第一种情况。
```cpp
const int N = 100003;
int p,A,B,a[N],n,m;
bitset<N> vis; ll pa[N],pb[N];
inline void Get(int A,int B){
vis.reset(),n=0,m=pa[0]=pb[0]=1,pb[1]=B;
while(!vis[pa[n]]) vis[pa[n]]=1,++n,pa[n]=pa[n-1]*A%p;
while(!vis[pb[m]]) ++m,pb[m]=pb[m-1]*B%p;
}
main(){
rd(p),rd(A),rd(B);
Get(A,B); if(n&1) swap(A,B),Get(A,B);
if(n*m!=p-1) puts("No"),exit(0); puts("Yes");
if(n==1){ for(ri i=0;i<m;++i) writesp(pb[i]); write(1),exit(0); }
if(m==1){ for(ri i=0;i<n;++i) writesp(pa[i]); write(1),exit(0); }
for(ri i=0;i<n;++i)
if(i&1) for(ri j=m-1;~j;--j) writesp(pa[i]*pb[j]%p);
else for(ri j=0;j<m;++j) writesp(pa[i]*pb[j]%p); write(1);
}
```