2026牛客暑期多校训练营4

2026牛客暑期多校训练营4Problem B. Quadratic Residue给定一个正整数p你的任务是找到三个正整数x1、x2 和q使得1≤x1 q1≤x2 pX1²≡p(modq)x 2²≡q(modp)。这里a≡b(modc) 表示a除以c的余数与b除以c的余数相同。我们可以让x1x2令x²pq这样就可以满足mod q p并且mod pq因为p已知我们就可以构造一个大于p的平方数这样q的值也可以求出来了注意q小于等于4时不能构造因为1≤x1 q1≤x2 p不一定能满足。Code:voidsolve(){intp;cinp;if(p2){cout12 1 71endl;return;}if(p3){cout4 2 13endl;return;}if(p4){cout3 3 5endl;return;}intxsqrt(p)2;intqx*x-p;coutx x qendl;}Problem D. The GameAlice 和Bob 正在玩一个游戏。初始时有一个空序列。他们会得到一个整数n并共同构造一个长度为n的排列p。Alice 先手。每一步中当前玩家需要从1 到n中选择一个此前尚未被选择过的整数并将其添加到序列末尾。恰好进行n步后该序列将成为1*,* 2*, . . . , n* 的一个排列p。对于排列p (p1*, p2, . . . , p**n*)它的一个循环移位是指选择一个下标i1≤i≤n并得到序列(p**i, p**i1*, . . . , 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出现以后两人会贪心选择最优解。我们可以暴力去枚举出前几种情况然后找规律nf§1121 231 3 241 3 2 451 4 2 3 561 4 3 5 2 671 5 2 4 6 3 781 5 4 6 3 7 2 891 6 2 5 7 4 8 3 9101 6 5 7 4 8 3 9 2 10偶数 n 2kf 1, (k1), k, (k2), (k-1), (k3), (k-2), ..., (2k), 2大数 k1, k2, …, 2k → 放到 f 的第 2, 4, 6, …, 2k 位奇数位1-indexed小数 k, k-1, …, 2 → 放到 f 的第 3, 5, 7, …, 2k-1 位偶数位奇数 n 2q1f 1, (q2), 2, (q1), (q3), q, (q4), (q-1), ..., (2q1), 3大数 q2, q3, …, 2q1小数 2, q1, q, q-1, …, 3codevoidsolve(){intn;cinn;if(n%20){intk1n/21,k2n/2;cout1 ;for(inti1;in;i){if(i%21){coutk1 ;k11;}else{coutk2 ;k2--;}}cout\n;}else{if(n1){cout1\n;return;}intqn/2;cout1;cout q2;cout 2;if(n5){cout q1;intlq3,sq;for(inti4;in;i){if(i%20)cout l;elsecout s--;}}cout\n;}}