Codeforces Round #278 (Div. 1), problem: (C) Prefix Product Sequence

i/(i-1) = j/(j-1) mod p,  p>=3 <=> i = j for p-1>= i >= j >= 2


這題在比賽時最後十五分鐘才打開看到

早知道就先來認真想= =

不過，把1, 4特例忽略掉真的頗G，一下就被Hack掉

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
int seive[100005] = {0};
int64 p;
int64 func(int64 a, int n){
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 gg = func(a, n/2);
    gg = (gg*gg)%p;
    if(n%2 == 0) return gg;
    if(n%2 == 1) return (gg*a)%p;
}
int main()
{
    for(int lx = 2;lx <= 100000;lx++)
        if(seive[lx] == 0)
            for(int ly = 2;ly*lx <= 100000;ly++)
                seive[ly*lx] = 1;
    scanf("%I64d", &p);
    if(p <= 4){
        puts("YES");
        if(p == 1)
            printf("1\n");
        else if(p == 2)
            printf("1\n2\n");
        else if(p == 3)
            printf("1\n2\n3\n");
        else
            printf("1\n3\n2\n4\n");
        return 0;
    }
    if(seive[p]){
        puts("NO");
        return 0;
    }
    puts("YES");
    printf("1\n");
    for(int64 lx = 2;lx < p;lx++){
        printf("%I64d\n", (lx*func(lx-1, p-2))%p);
    }
    printf("%I64d\n", p);
    return 0;
}