2020牛客暑期多校第十场 A - Permutation（思维）
传送门
首先找一下规律，假设 p = 7 p=7 p=7，那么写出 1 − 6 1-6 1−6分别乘二乘三的余数，然后找下规律：
| 原数 | 乘二取余 | 乘三取余 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 4 | 6 |
| 3 | 6 | 2 |
| 4 | 1 | 5 |
| 5 | 3 | 1 |
| 6 | 5 | 4 |
然后我们发现从对于这个例子来说，从任意地方出发都能找到一条或多条路径。如果仅仅考虑第一、二列和第一、三列，那么我们发现每种情况都会形成若干个环：
那么就是如何破环连成一条路径的问题，我们可以任选一个数作为起点，先贪心的找乘二取余(或者乘三取余)的路径，一旦将形成环，就连接到乘三取余的环上继续，直到无论如何都是环或者找到了
p
−
1
p-1
p−1个数
注意要考虑取模后为0的情况
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1e6+10;
bool vis[maxn];
vector<int> ans;
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(vis,0,sizeof vis);
ans.clear();
ans.push_back(1);
vis[1]=1;
int pre=1;
bool ok;
while(1){
ok=0;
if(!vis[pre*2%n] && pre*2%n){
ans.push_back(pre*2%n);
pre=pre*2%n,ok=1;
vis[pre]=1;
}else if(!vis[pre*3%n] && pre*3%n){
ans.push_back(pre*3%n);
pre=pre*3%n,ok=1;
vis[pre]=1;
}
if(ans.size()==n-1){
ok=1;
break;
}
if(!ok) break;
}
if(ok){
for(auto i: ans) printf("%d ",i);
puts("");
}else puts("-1");
}
return 0;
}