2015年4月20日 星期一

2015/04/20 Codeforces 487C. Prefix Product Sequence

/*
    對於質數 保證有解
    對於大於4的非質數 保證沒有解
*/
// http://codeforces.com/problemset/problem/487/C
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int N;
bool is_prime[200000];
int rev[200000];

void set()
{
    fill(is_prime, is_prime+200000, true);
    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i < 1000; i++)
    {
        if( !is_prime[i] ) continue;

        for(int j = i*i; j < 200000; j += i)
            is_prime[j] = false;
    }
}

int main()
{
    set();

    scanf("%d", &N);

    if( N == 1 ) puts("YES\n1");
    else if( N == 4 ) puts("YES\n1\n3\n2\n4");
    else if( !is_prime[N] ) puts("NO");
    else
    {
        puts("YES");

        rev[1] = 1;
        for(int Ni = 2; Ni < N; Ni++)
            rev[Ni] = (ll)rev[N%Ni]*(N-N/Ni)%N;

        puts("1");
        for(int Ni = 1; Ni < N; Ni++)
            cout<<((ll)rev[Ni]*(Ni+1)-1 )%N+1<<endl;
    }
}

沒有留言:

張貼留言