http://codeforces.com/problemset/problem/487/C 感觉是很糟糕的一个题... 首先，一个合法的构造，一定是开头是\(1\)，结尾是\(N\)，因为如果中间出现\(1\)或者\(N\)的话，一定会有重复。 然后我就觉得所有的合数都是不行的，因为任何的合数都可以拆成\(p \times q\)，但是有的合数，只能拆成两个相同的数乘起来，比如\(4=2 \times 2\)、\(9=3 \times 3\)，但是对于\(9\)来说，\(6\)中也存在\(3\)，所以\(9\)还是不合法，于是合数中只有\(4\)需要特判，之后都不成立。 然后我们观察\((i+1)\times inv[i]\)这个式子。 因为\[(i+1)\times inv[i]=(j+1)\times inv[j]\] \[i \times j \times (i+1)\times inv[i]=i \times j \times (j+1)\times inv[j]\] \[j \times (i+1)=i \times (j+1)\]
上面的式子只有\(i=j\)时才成立。 于是\((i+1)\times inv[i]\)就会形成一个\(2\)到\(N-1\)的排列，这么构造就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
typedef long long LL;
using namespace std;
LL kpow(LL x,int y,int p)
{
if(y==0) return 1;
LL w=kpow(x,y/2,p);
w=w*w;
w%=p;
if(y%2) w*=x;
w%=p;
return w;
}
int n;
int main()
{
scanf("%d",&n);
if(n==4)
{
cout<<"YES"<<endl;
cout<<1<<endl;
cout<<3<<endl;
cout<<2<<endl;
cout<<4<<endl;
return 0;
}
int bj=0;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
cout<<"NO";
return 0;
}
}
printf("YES\n");
printf("1\n");
for(int i=2;i<n;i++)
{
LL ans=1;
ans*=i;
ans*=kpow(i-1,n-2,n);
ans%=n;
printf("%I64d\n",ans);
}
if(n!=1) printf("%d",n);
return 0;
}
|