Codeforces Round #278 (Div. 2) E. Prefix Product Sequence

题意：http://mp.weixin.QQ.com/s/M_RYFovq_G9w5EYUDRcgHw

题解：http://mp.weixin.qq.com/s/ITNKOywnVn0QDC-hYYl_5Q

另一篇题解：http://blog.csdn.net/qq_24451605/article/details/48023529

逆元相关：http://blog.csdn.net/acdreamers/article/details/8220787

补充1：第二篇题解实际是带mod运算的，blog主省略了

补充2：为什么大于4的合数无解？若n为合数，必然可以分解为pq，若p！=q，又因为p和q都小于n，那么必然 pq | (n - 1)!；若p == q，因为n > 4，则 p > 2，2p < n，所以也有 pq | (n - 1)!，综述大于4的合数无解。

#include <bits/stdc++.h>using namespace std;const int N = 100005;int inv[N];int main() {	int n;	cin >> n;	if(n == 1) {		puts("YES/n1/n");	} else if(n == 4) {		puts("YES/n1/n3/n2/n4");	} else {		int limit = sqrt(n);		for(int i = 2; i <= limit; i++) {			if(n % i == 0) {				puts("NO");				return 0;			}		}		puts("YES/n1");		inv[1] = 1;		for(int i = 2; i < n; i++) {			inv[i] = 1LL * (n - n / i) * inv[n % i] % n;			PRintf("%d/n", 1LL * i * inv[i - 1] % n);		}		printf("%d/n", n);	}	return 0;}