P3599 Koishi Loves Construction

题目链接：https://www.luogu.com.cn/problem/P3599

题解：

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<queue>
#include<sstream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
#include<cstring>
#include<cstdio>
#define N 10000
#define  ll long long
#define PI acos(-1)
#define mset(s, _) memset(s, _, sizeof(s))
//#define lo
using namespace std;
void coutx(double q, int x)
{
    //cout.setf(ios::fixed);
    //cout.unsetf(ios::fixed);
    cout << fixed << setprecision(x) << q << endl;
    return ;
}
inline ll ksc(ll x, ll y, ll mod)//快速乘
{
    return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;
}
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}

int X, T;
int n;

bool isprime(int k)
{
    for(int i = 2; i <= sqrt(k); i ++)
    {
        if(k % i == 0)
            return false;
    }
    return true;
}
ll inv[100010];
void work()
{
    if(n != 4)
    {
        cout << 2 << ' ' << 1 << ' ';
        inv[1] = 1;
        for(int i = 2; i < n; i ++)
        {
            inv[i] = (ll)((n - n / i) * inv[n % i]) % n;
            cout << (i * inv[i - 1] + n) % n << ' ';
        }
        cout << n << endl;
    }
    if(n == 4)
        cout << "2 1 3 2 4" << endl;
    return;
}
int main()
{
    #ifdef lo
     freopen("data.in","r",stdin);
     freopen("data.out","w",stdout);
    #endif
    srand((unsigned int)time(0));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> X >> T;
    if(X == 1)
    {
        while(T --)
        {
            cin >> n;
            int a = n;
            int b = 1;
            if(n == 1)
                cout << "2 1" << endl;
            else if(n % 2)
                cout << 0 << endl;
            else
            {
                cout << 2;
                while(b <= n - 1)
                {
                    cout << ' ' << a << ' ' << b;
                    a -= 2;
                    b += 2;
                }
                cout << endl;
            }
         } 
    }
    else
    {    
        while(T --)
        {
            cin >> n;
            if(n == 4 || isprime(n))
                work();
            else
                cout << 0 << endl;
        }
    }
    return 0;
 }