487C Prefix Product Sequence

传送门

题目大意

分析

 

因为n为质数所以i-1的逆元唯一

因此ai唯一

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
#define int long long
using namespace std;
int inv[100100];
inline bool p(int x){
    for(int i=2;i*i<=x;i++)
      if(x%i==0)return 0;
    return 1;
}
signed main(){
    int n,m,i,j,k;
    scanf("%lld",&n);
    if(n==1){
      puts("YES");
      printf("1
");
      return 0;
    }
    if(n==4){
      puts("YES");
      printf("1
3
2
4
");
      return 0;
    }
    if(!p(n)){
      puts("NO");
      return 0;
    }
    puts("YES");
    puts("1");
    inv[1]=1;
    for(i=2;i<n;i++){
      inv[i]=(n-n/i)*inv[n%i]%n;
      printf("%lld
",i*inv[i-1]%n);
    }
    printf("%lld
",n);
    return 0;
}