裁决已至！
称量，你的罪恶！
以此身，肃正万象！
人总是越活越抽象的，所以怎么还不考期末，我要考期末！
A. Min
http://222.180.160.110:1024/contest/3641/problem/1
给出 \(n\) 个数 \(A_{1\sim n}\)，现求一组整数序列 \(X_{1\sim n}\) 使得 \(S = A_1 \times X_1 + A_2 \times X_2 + \cdots + A_n \times X_n > 0\)，且 \(S\) 的值最小。求 \(S_{\min}\)。
题目给得莫名奇妙。不过我们既然要让其尽可能接近 \(0\)，而又不等于 \(0\)，怎么做呢？
先将数组中所有元素取绝对值。对于两个互质的正数 \(a, b\)，能否找到一组 \((x, y)\)，满足 \(ax + by = 1\) 呢？
这是什么？裴蜀定理！所以一定能找到一组整数解 \((x, y)\)，满足上述不定方程。
对于任意两个数 \(a_1, b_1\)，假设其最大公约数为 \(g\)，那我们一定能找到一组 \((x_1, y_1)\)，满足 \(\dfrac {a_1} {g} \times x_1 + \dfrac {b_1} {g} \times y_1 = 1\)。相应地，一定有 \(a_1 x_1 + b_1 y_1 = g\)。并且 \(\text{RSH}\) 的最小正数值就是 \(g\)，因为 \(a_1, b_1\) 不可能通过任意加乘操作（即初等行变换操作）得到一个不包含因子 \(g\) 的值。
故对于给定的数组，求解其所有元素绝对值的 \(\gcd\) 即可。
using namespace fastIO;
int n, g, x;
inline int abs(int x) {
return x >= 0 ? x : -x;
}
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
int main() {
read(n);
while (n--) {
read(x);
g = gcd(g, abs(x));
}
print(g);
return 0;
}
} // namespace XSC062
B. 向量
http://222.180.160.110:1024/contest/3641/problem/2
给定一对数 \((a, b)\)，你可以任意使用 \((a, b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)\) 这些数对，使得它们之和为 \((x, y)\)。
我记得我写过题解来着…… 找到了。
首先，我们不将 \(x, y\) 合并处理，各凑各的。
可以得到：
\[n_1 \times a + m_1 \times b = x \\ n_2 \times a + m_2 \times b = y \]而以上两式 分别 是否有解，可以用裴蜀定理方便地判断，即 \((a,b)\mid x\) 和 \((a,b)\mid y\) 是否成立。
可是分别有解并不代表能同时有解。为了探究两式是否能同时有解，我们先直接将两式相加。
\[(n_1 + n_2) \times a + (m_1 + m_2) \times b = x + y \]但这个式子是否有解仅等价于上两式是否同时有解，并不一定在题面的应用场景中成立（即未对系数加以限制，导致不一定存在一组满足题意的解），与我们的目的不符。
不难发现，题目中的向量可以分为两种：\(a, b\) 同号、\(a, b\) 异号。
于是我们将 \(\text {LSH}\) 替换为同号、异号的向量相加的结果，得到：
\[n_3 \times (a + b) + m_3 \times (a - b) = x + y \]裴蜀定理判断该式和最开头的两个式子是否有解即可。
注意到 \(x + y\) 的操作，实际上是需要开 long long 的。
#define int long long
namespace XSC062 {
using namespace fastIO;
int T, a, b, x, y, g1, g2;
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
int main() {
read(T);
while (T--) {
read(a), read(b);
read(x), read(y);
g1 = gcd(a, b);
g2 = gcd(a + b, a - b);
if (((x + y) % g2 == 0) &&
(x % g1 == 0) && (y % g1 == 0))
puts("Y");
else puts("N");
}
return 0;
}
} // namespace XSC062
#undef int
C. 青蛙的约会
http://222.180.160.110:1024/contest/3641/problem/3
两只青蛙在长度为 \(L\) 的环形数轴上往前跳，一只从 \(x\) 开始，一次跳 \(m\) 步；另一只从 \(y\) 开始，一次跳 \(n\) 步。每一次两只青蛙都会同时往前跳一步，求它们跳了几次才能碰头。
省流：\(x + m \times a \equiv y + n \times a \pmod L\)。设成负数是为了好操作。
那么有 \(x + m \times a - y - n \times a = b \times L\)。
化简为 \((m - n) \times a - L \times b = y - x\)。
exgcd 即可。
#define int long long
namespace XSC062 {
using namespace fastIO;
int x, y, m, n, L, k1, k2, g;
inline void swap(int &x, int &y) {
x ^= y ^= x ^= y;
return;
}
inline int exgcd(int x, int y) {
if (y == 0) {
k1 = 1, k2 = 0;
return x;
}
int u = exgcd(y, x % y), t = k1;
k1 = k2, k2 = t - (x / y) * k2;
return u;
}
int main() {
read(x), read(y);
read(m), read(n), read(L);
if (m - n < 0)
swap(m, n), swap(x, y);
g = exgcd(m - n, L);
if ((y - x) % g) {
puts("Impossible");
return 0;
}
k1 *= (y - x) / g, L /= g;
k1 = ((k1 % L) + L) % L;
print(k1);
return 0;
}
} // namespace XSC062
#undef int
D. 荒岛野人
http://222.180.160.110:1024/contest/3641/problem/4
有 \(N\) 个野人住在长度为 \(M\) 的环形数轴上，每个以 \(C_i\) 为起点，往前走 \(P_i\) 步，能活 \(L_i\) 年，问 \(M\) 至少要多大，才能保证在所有野人死掉前没有两个人撞到一起。保证 \(M\) 有解且 \(M \le 10^6\)。
这个 \(M\) 的范围限制给的，就差把「枚举 \(M\) 并 \(\mathcal O(N^2)\) 验证正确性」写出来了。
那么问题就在于如何验证正确性。很简单，我们对于任意两个野人 \(i, j\)，exgcd 一下，看看相撞的日期是否短于两方的寿命即可。判定方式和青蛙那道题类似，所以我直接复制粘贴了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 25;
const int inf = 1e18;
int n, mx;
int c[maxn], p[maxn], l[maxn];
inline int min(int x, int y) {
return x < y ? x : y;
}
inline int max(int x, int y) {
return x > y ? x : y;
}
inline void swap(int &x, int &y) {
x ^= y ^= x ^= y;
return;
}
inline int exgcd(int x, int y,
int &k1, int &k2) {
if (y == 0) {
k1 = 1, k2 = 0;
return x;
}
int u = exgcd(y, x % y, k1, k2);
int t = k1;
k1 = k2, k2 = t - (x / y) * k2;
return u;
}
inline int calc(int m, int n,
int x, int y, int L) {
if (m - n < 0)
swap(m, n), swap(x, y);
int k1, k2;
int g = exgcd(m - n, L, k1, k2);
if ((y - x) % g)
return inf;
k1 *= (y - x) / g, L /= g;
k1 = ((k1 % L) + L) % L;
return k1;
}
inline bool check(int m) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (calc(p[i], p[j], c[i],
c[j], m) <= min(l[i], l[j]))
return 0;
}
}
return 1;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(c[i]), read(p[i]);
read(l[i]), mx = max(mx, c[i]);
}
for (int i = mx; ; ++i) {
if (check(i)) {
print(i);
break;
}
}
return 0;
}
} // namespace XSC062
#undef int
E. Sumdiv
http://222.180.160.110:1024/contest/3641/problem/5
求 \(A^B\) 的所有约数之和 \(\bmod 9901\)。
假设 \(A = p_1 ^ {d_1} \times p_2 ^ {d_2} \times \cdots \times p_N ^ {d_N}\)，那么有 \(A^B = p_1 ^ {d_1\times B} \times p_2 ^ {d_2\times B} \times \cdots \times p_N ^ {d_N\times B}\)。
那么可以得到答案值为 \(\prod_{i=1}^N (p_i ^ {d_i \times B + 1} - 1) \div (p_i - 1)\)。后面的内容就是对于 \(p_i\) 的所有因数和。
怎么得到的呢？明显 \(p_i\) 的因数和其实就是幂次和，即 \(\sum_{j = 1}^{d_i\times B}{p_i}^j\)。这是什么？等比数列！整一个求和公式就可以了。
取模的话好处理，随便逆元一下就可以了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int mod = 9901;
int A, B, res = 1;
inline int qkp(int x, int y) {
int res = 1;
while (y) {
if (y & 1)
(res *= x) %= mod;
(x *= x) %= mod;
y >>= 1;
}
return res;
}
inline int getinv(int x) {
return qkp(x, mod - 2);
}
inline int calc(int p, int d) {
return ((qkp(p, d + 1) - 1) *
getinv(p - 1)) % mod;
}
int main() {
read(A), read(B);
for (int i = 2; i <= A; ++i) {
if (A % i)
continue;
int tot = 0;
while (A % i == 0)
++tot, A /= i;
(res *= calc(i, tot * B)) %= mod;
}
print(res);
return 0;
}
} // namespace XSC062
#undef int
F. 排课表
http://222.180.160.110:1024/contest/3641/problem/6
在 \(n\) 节课中选 \(m\) 节来上，\(n\) 节课中有 \(a\) 节不能放在第一节，\(b\) 节不能放在最后一节，两者无重合，求排课方案数。
小容一个斥。算出总方案数，减去第一节课选了 \(a\) 节中某一节的方案数，再减去最后一节课选了 \(b\) 节中的某一节的方案数，最后加上第一节选了 \(a\) 节中的某一节、同时最后一节课选了 \(b\) 节中的某一节的方案数即可。
那么答案的值就是 \(A_n^m - a * A_{n - 1} ^ {m - 1} - b * A_{n - 1} ^ {m - 1} + a * b * A(n - 2, m - 2)\)。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 1e5;
const int maxn = 1e5 + 5;
const int mod = 998244353;
int fac[maxn];
int T, n, m, a, b, res;
inline int qkp(int x, int y) {
int res = 1;
while (y) {
if (y & 1)
(res *= x) %= mod;
(x *= x) %= mod;
y >>= 1;
}
return res;
}
inline int getinv(int x) {
return qkp(x, mod - 2);
}
inline int A(int n, int m) {
return (fac[n] * getinv(fac[n - m])) % mod;
}
int main() {
#ifdef ONLINE_JUDGE
freopen("arrange.in", "r", stdin);
freopen("arrange.out", "w", stdout);
#endif
read(T);
fac[0] = 1;
for (int i = 1; i <= lim; ++i)
fac[i] = (fac[i - 1] * i) % mod;
while (T--) {
read(n), read(m);
read(a), read(b);
res = A(n, m) - a * A(n - 1, m - 1);
res = (res % mod + mod) % mod;
res -= A(n - 1, m - 1) * b;
res = (res % mod + mod) % mod;
res += a * A(n - 2, m - 2) * b;
res %= mod;
print(res, '\n');
}
return 0;
}
} // namespace XSC062
#undef int
标签：return,复习,数论,230526,times,int,k1,read,inline From： https://www.cnblogs.com/XSC062/p/17435598.html