codeforces 487C C. Prefix Product Sequence(构造+数论)

时间：2023-03-09 07:50:41
codeforces 487C C. Prefix Product Sequence(构造+数论)

题目链接：

C. Prefix Product Sequence

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Consider a sequence [a1, a2, ... , an]. Define its prefix product sequence codeforces 487C C. Prefix Product Sequence(构造+数论).

Now given n, find a permutation of [1, 2, ..., n], such that its prefix product sequence is a permutation of [0, 1, ..., n - 1].

Input

The only input line contains an integer n (1 ≤ n ≤ 105).

Output

In the first output line, print "YES" if such sequence exists, or print "NO" if no such sequence exists.

If any solution exists, you should output n more lines. i-th line contains only an integer ai. The elements of the sequence should be different positive integers no larger than n.

If there are multiple solutions, you are allowed to print any of them.

Examples
input
7
output
YES
1
4
3
6
5
2
7
input
6
output
NO

题意：

能否找到一个[1,n]的一个排列.使得前缀积是一个关于n的完全剩余系;

思路：

假设这个完全剩余系最后是1,2,3,...n-1,0;我们看能不能找到这样的排列,由逆元我们知道,

i=1*inv[1]*2*inv[2]*...(i-1)*inv[i-1]*i;交错排列取出来,ans[i]=inv[i-1]*i;最后一个是ans[n]=n;这样就好了;

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bits/stdc++.h>

#include <stack>

#include <map>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());

    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());

    F && (num=-num);

}

int stk[70], tp;

template<class T> inline void print(T p) {

    if(!p) { puts("0"); return; }

    while(p) stk[++ tp] = p%10, p/=10;

    while(tp) putchar(stk[tp--] + '0');

    putchar('\n');

}

//const LL mod=1e9+7;

const double PI=acos(-1.0);

const LL inf=1e18;

const int N=1e5+20;

const int maxn=4e3+220;

const double eps=1e-12;

int n;

LL ans[N];

int isprime(int x)

{

    int le=(int)sqrt(x*1.0+0.5);

    for(int i=2;i<=le;i++)

    {

        if(x%i==0)return 0;

    }

    return 1;

}

LL pow_mod(int x,int y,int mod)

{

    LL s=1,base=x;

    while(y)

    {

        if(y&1)s=s*base%mod;

        base=base*base%mod;

        y>>=1;

    }

    return s;

}

int main()

{

    read(n);

    if(n==1)printf("YES\n1\n");

    else if(n==4)printf("YES\n1\n3\n2\n4\n");

    else

    {

        if(!isprime(n)){cout<<"NO\n";return 0;}

        cout<<"YES\n";

        ans[1]=1;

        For(i,2,n-1)ans[i]=(LL)(i)*pow_mod(i-1,n-2,n)%n;

        ans[n]=n;

        For(i,1,n)print(ans[i]);

    }

    return 0;

}

　　

相关文章