2026牛客暑期多校训练营4
Problem B. Quadratic Residue
给定一个正整数p，你的任务是找到三个正整数x1、x2 和q，使得：
1≤x1< q，1≤x2< p；
X1²≡p(modq)；
x 2²≡q(modp)。
这里，a≡b(modc) 表示a除以c的余数与b除以c的余数相同。
我们可以让x1=x2，令x²=p+q，这样就可以满足mod q =p，并且mod p=q
因为p已知，我们就可以构造一个大于p的平方数，这样q的值也可以求出来了，注意q小于等于4时，不能构造，因为1≤x1< q，1≤x2< p不一定能满足。
Code:
voidsolve(){intp;cin>>p;if(p==2){cout<<12<<" "<<1<<" "<<71<<endl;return;}if(p==3){cout<<4<<" "<<2<<" "<<13<<endl;return;}if(p==4){cout<<3<<" "<<3<<" "<<5<<endl;return;}intx=sqrt(p)+2;intq=x*x-p;cout<<x<<' '<<x<<' '<<q<<endl;}Problem D. The Game
Alice 和Bob 正在玩一个游戏。
初始时，有一个空序列。他们会得到一个整数n，并共同构造一个长度为n的排列p。
Alice 先手。每一步中，当前玩家需要从1 到n中选择一个此前尚未被选择过的整数，并将其添加到序列
末尾。恰好进行n步后，该序列将成为1*,* 2*, . . . , n* 的一个排列p。
对于排列p= (p1*, p2, . . . , p**n*)，它的一个循环移位是指：选择一个下标i（1≤i≤n），并得到序
列(p**i, p**i+1*, . . . , pn, p1, p2, . . . , pi−*1)。
对于一个排列p，定义f(p) 为p的所有循环移位中字典序最小的一个。
Alice 希望让f(p) 的字典序尽可能小，而Bob 希望让它的字典序尽可能大。
假设双方都采取最优策略，请求出最终得到的排列f(p)。
根据题意，我们可以知道：f§ 一定从 1 开始。若最终排列为p=(a1,a2,…,ak,1,b1,b2,…,bt)，则 f§ = (1,b1,b2,…,bt,a1,a2,…,ak)。所以在1出现前，Alice会先放置尽可能大的数，Bob会放置尽可能小的数。1出现以后两人会贪心选择最优解。
我们可以暴力去枚举出前几种情况然后找规律：
| n | f§ |
|---|---|
| 1 | 1 |
| 2 | 1 2 |
| 3 | 1 3 2 |
| 4 | 1 3 2 4 |
| 5 | 1 4 2 3 5 |
| 6 | 1 4 3 5 2 6 |
| 7 | 1 5 2 4 6 3 7 |
| 8 | 1 5 4 6 3 7 2 8 |
| 9 | 1 6 2 5 7 4 8 3 9 |
| 10 | 1 6 5 7 4 8 3 9 2 10 |
偶数 n = 2k
f = 1, (k+1), k, (k+2), (k-1), (k+3), (k-2), ..., (2k), 2- 大数 = k+1, k+2, …, 2k → 放到 f 的第 2, 4, 6, …, 2k 位（奇数位，1-indexed）
- 小数 = k, k-1, …, 2 → 放到 f 的第 3, 5, 7, …, 2k-1 位（偶数位）
奇数 n = 2q+1
f = 1, (q+2), 2, (q+1), (q+3), q, (q+4), (q-1), ..., (2q+1), 3- 大数 = q+2, q+3, …, 2q+1
- 小数 = 2, q+1, q, q-1, …, 3
code：
voidsolve(){intn;cin>>n;if(n%2==0){intk1=n/2+1,k2=n/2;cout<<1<<' ';for(inti=1;i<n;i++){if(i%2==1){cout<<k1<<' ';k1+=1;}else{cout<<k2<<' ';k2--;}}cout<<'\n';}else{if(n==1){cout<<"1\n";return;}intq=n/2;cout<<1;cout<<' '<<q+2;cout<<' '<<2;if(n>=5){cout<<' '<<q+1;intl=q+3,s=q;for(inti=4;i<n;i++){if(i%2==0)cout<<' '<<l++;elsecout<<' '<<s--;}}cout<<'\n';}}
