dede仿站,微网站开发工具,北碚集团网站建设,企业网站租服务器正题
题目链接:https://www.luogu.com.cn/problem/P3599 题目大意
构造一个nnn的排列#xff0c;要求满足其中一个给定的要求
对于每个前缀和在模nnn意义下不同对于每个前缀积在模nnn意义下不同 解题思路
对于加法#xff0c;显然nnn要填在第一位#xff0c;那么这一位的…正题
题目链接:https://www.luogu.com.cn/problem/P3599 题目大意
构造一个nnn的排列要求满足其中一个给定的要求
对于每个前缀和在模nnn意义下不同对于每个前缀积在模nnn意义下不同 解题思路
对于加法显然nnn要填在第一位那么这一位的前缀和就是000了。并且如果nnn是奇数那么有(∑i1ni)%n0(\sum_{i1}^ni)\%n0(∑i1ni)%n0所以nnn不能是奇数。对于nnn是偶数的情况我们可以将一个数iii在模nnn意义下视为−(n−i)-(n-i)−(n−i)。所以我们可以构造一个波动序列也就是n,1,−2,3,−4,5,−6...n,1,-2,3,-4,5,-6...n,1,−2,3,−4,5,−6... 对于乘法nnn要填在最后111要填在第一位然后如果nnn是一个合数那么有(∏i1ni)%n0(\prod_{i1}^ni)\%n0(∏i1ni)%n0也就是有两个000所以无解。那么nnn是一个质数的情况我们知道在模nnn意义下对于每个数都有一个不同的逆元考虑构建一个ai1i−1∗ia_i\frac{1}{i-1}*iaii−11∗i的序列这样siis_iisii。
如何证明aia_iai在模nnn意义下各不相同设aiajka_ia_jkaiajk那么有(i−1)k%ni,(j−1)k%nj(i-1)k\%ni,(j-1)k\%nj(i−1)k%ni,(j−1)k%nj ⇒(i−j)k%n(i−j)\Rightarrow (i-j)k\%n(i-j)⇒(i−j)k%n(i−j) 要求k≠1k\neq 1k1所以不成立。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
ll idx,n,T;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%n;xx*x%n;b1;}return ans;
}
int main()
{scanf(%lld%lld,idx,T);while(T--){scanf(%lld,n);if(idx1){if(n1)printf(2 1);else if(n1)printf(0);else {printf(2 );ll k0;for(ll i1;in;i){if(i1)printf(%lld ,n-k);else printf(%lld ,k);k;}}}else{bool flag0;if(n1)printf(2 1);else if(n4)printf(2 1 3 2 4);else{for(ll i2;i*in;i)if(n%i0){flag1;break;}if(flag){printf(0\n);continue;}printf(2 1 );ll last1;for(ll i2;in;i){ll kpower(last,n-2)*i%n;lastlast*k%n;printf(%lld ,k);}printf(%lld,n);}}putchar(\n);}
}
