正題

題目鏈接:https://www.luogu.com.cn/problem/P3599

---

題目大意

構(gòu)造一個(gè)$n$的排列，要求滿足其中一個(gè)給定的要求

對(duì)于每個(gè)前綴和在模$n$意義下不同

對(duì)于每個(gè)前綴積在模$n$意義下不同

---

解題思路

對(duì)于加法，顯然$n$要填在第一位，那么這一位的前綴和就是$0$了。并且如果$n$是奇數(shù)那么有$({\sum }_{i=1}^{n}i)\%n=0$所以$n$不能是奇數(shù)。對(duì)于$n$是偶數(shù)的情況，我們可以將一個(gè)數(shù)$i$在模$n$意義下視為$?(n?i)$。所以我們可以構(gòu)造一個(gè)波動(dòng)序列也就是$$n,1,?2,3,?4,5,?6...$$
對(duì)于乘法，$n$要填在最后，$1$要填在第一位，然后如果$n$是一個(gè)合數(shù)，那么有$({\prod }_{i=1}^{n}i)\%n=0$也就是有兩個(gè)$0$，所以無(wú)解。那么$n$是一個(gè)質(zhì)數(shù)的情況，我們知道在模$n$意義下對(duì)于每個(gè)數(shù)都有一個(gè)不同的逆元，考慮構(gòu)建一個(gè)$a_i=\frac{1}{i?1}?i$的序列，這樣$s_i=i$。

如何證明$a_i$在模$n$意義下各不相同，設(shè)$a_i=a_j=k$那么有$$(i?1)k\%n=i,(j?1)k\%n=j$$
$$?(i?j)k\%n=(i?j)$$
要求$k=1$所以不成立。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll idx,n,T; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%n;x=x*x%n;b>>=1;}return ans; } int main() {scanf("%lld%lld",&idx,&T);while(T--){scanf("%lld",&n);if(idx==1){if(n==1)printf("2 1");else if(n&1)printf("0");else {printf("2 ");ll k=0;for(ll i=1;i<=n;i++){if(i&1)printf("%lld ",n-k);else printf("%lld ",k);k++;}}}else{bool flag=0;if(n==1)printf("2 1");else if(n==4)printf("2 1 3 2 4");else{for(ll i=2;i*i<=n;i++)if(n%i==0){flag=1;break;}if(flag){printf("0\n");continue;}printf("2 1 ");ll last=1;for(ll i=2;i<n;i++){ll k=power(last,n-2)*i%n;last=last*k%n;printf("%lld ",k);}printf("%lld",n);}}putchar('\n');} }

總結(jié)

以上是生活随笔為你收集整理的P3599-Koishi Loves Construction【构造,数论】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。