$A$

何老板有 $n$ 根大小相同且质地均匀的火腿肠，要分给 $m$ 名信竞队员。要求每名队员分得的香肠重量相同。
何老板想知道，最少切多少刀就能满足上述要求？
$\texttt{Data Range:}1\le n,m\le 1000$

没什么好说的，贪心原则，如果要切的点恰好是火腿肠的端点就可以不切。

所以答案就是 $m-gcd(n,m)$，考试的时候写了个nt的暴力模拟，由于数据范围过于良心也能过。

代码

#include <cstdio>

int main() {
	int n, m, ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n * m; ++ i)
		if (i % n == 0 && i % m) ++ ans;
	printf("%d", ans);
	return 0;
}

$B$

给你一个整数数列 $a_1,a_2…a_n$。请你构造一个整数数列 $b_1,b_2…b_n$，使得 $\sum\limits^n_{i=1}a_i\times b_i$ 在 $>0$ 的前提下尽量小。
$\texttt{Data Range:} 1\le n\le n\le 100$

裴蜀定理模板题。输出所有 $a_i$ 的 gcd 即可。

把所有 $a_i$ 都除以它们的 gcd 后这个结论就很显然了。

代码

#include <cstdio>

int gcd(int n, int m) {return m ? gcd(m, n % m) : n;}

int main() {
	int n, ans = 0;
	scanf("%d%d", &n, &ans);
	for (int i = 1; i < n; ++ i) {
		int x;
		scanf("%d", &x);
		ans = gcd(ans, x);
	}
	printf("%d", ans >= 0 ? ans : -ans);
	return 0;
}

$C$

算术基本定理(也叫唯一分解定理)内容如下：
“任何一个大于 $1$ 的自然数 $x$,可以唯一分解成有限个质数的乘积” ,
也就是：$x=P_1^{k_1}P_2^{k_2}…P_n^{k_n}$ 。其中 $P_i$ 是 $x$ 的质因数，$k_i$ 为正整数。
定义函数 $f(x)=\prod^n_{i=1}(k_i+1)$。求 $\sum\limits^r_{i=l}f(i)$ 对 $998244353$ 取模的值。
$\texttt{Data Range:} 1\le l,r\le 10^{14}$

看数据范围，刚好能让根号算法跑过去，如果是 log 的算法或者结论题不大可能给你这么小的数据范围。

那么不难证明 $f(x)$ 等于 $x$ 的因数个数。~~如果你有点小学奥数基础就可以直接用结论了~~

由于原式比较奇怪，转化为 $\sum\limits^r_{i=1}f(i)-\sum\limits^l_{i=1}f(i)$。问题变为求 $1…n$ 中所有数因数个数之和。

考虑类似筛法的思想，对于每个数计算他贡献了多少，也就是有多少个数被它整除。因此 $\sum\limits^n_{i=1}f(i)=\sum\limits^n_{i=1}\lfloor \frac{n}{i} \rfloor$。上数论分块即可。

代码

#include <cstdio>
#define int long long

const int mod = 998244353LL;

int g(int n) {
	int ans = 0LL;
	for (int l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans = (ans + (r - l + 1) * (n / l) % mod) % mod;
	}
	return ans;
}

signed main() {
	int l, r;
	scanf("%lld%lld", &l, &r);
	printf("%lld", (g(r) - g(l - 1) + mod) % mod);
}

$D$

构造两个长度为 $n$ 的数列 $a,b$，要求对于任意的 $i,j$，$a_i\ne a_j,b_i\ne b_j$，对于任意的 $i$，$a_i\ne b_i$，$a,b$ 中的数都在 $1\sim m$ 之间。求方案数 $\operatorname{mod} 10^9+7$。
$\texttt{Data Range:}1\le n\le m\le 5\times 10^5$

容斥题。不考虑 $a_i\ne b_j$ 的限制，方案数为 $(A_m^n)^2$。

然后考虑 $a_i=b_j$ 的情况。容斥减去 $b$ 数组的不合法方案，显然满足这种情况至少有一个 $i$ 满足 $a_i=b_i$，再减去两个 $i$ 满足 $a_i=b_i$ 的，再加上三个 $i$ 满足的……

于是总的方案数为 $A^n_m\times \sum\limits^n_{i=0}(-1)^i\tbinom{n}{i} A_{m-i}^{n-i}$。

代码

#include <cstdio>
#define int long long

const int mod = 1e9 + 7;
int fact[500005], inv[500005];

int qpow(int a, int b) {
	int ret = 1LL;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

signed main() {
	int n, m, ret = 1LL, ret2 = 0LL;
	fact[0] = 1;
	for (int i = 1; i <= 500000; ++ i) fact[i] = fact[i - 1] * i % mod;
	inv[500000] = qpow(fact[500000], mod - 2);
	for (int i = 499999; i >= 0; -- i)
		inv[i] = inv[i + 1] * (i + 1) % mod;
	scanf("%lld%lld", &n, &m);
	for (int i = m - n + 1; i <= m; ++ i) ret = ret * i % mod;
	for (int i = 0; i <= n; ++ i) {
		int f = (i & 1 ? -1 : 1);
		ret2 = (ret2 + f * fact[n] * fact[m - i] % mod * inv[n - i] % mod * inv[i] % mod * inv[m - n] % mod) % mod;
	}
	ret = ret * (ret2 + mod) % mod;
	printf("%lld", ret);
	return 0;
}

$E$

给你两个数列长度为 $n$ 的数列 $a,b$，将任意两个 $a_i,b_j$ 组为一对，一个 $a_i,b_i$ 只能参与到一对中。要求恰有 $k$ 对满足 $a_i>b_j$。$a,b$ 数列所有的数互不相同。求方案数 $\operatorname{mod} 10^9+7$
$\texttt{Data Range:}1\le n\le 2000$。

先把 $a,b$ 从小到大排个序。

假设 $cnt_i$ 表示满足 $a_i>b_j$ 的 $j$ 的数量。这个可以像我一样暴力也可以二分查找。

$f_{i,j}$ 表示在 $a_1,a_2…a_i$ 中恰好选出 $j$ 个数，与 $b_1,b_2…b_j$ 组成至少 $k$ 个 $a_i>b_j$ 对的方案数。状态定义比较玄学。

$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times (cnt_i-(j-1))$。

定义 $g_i$ 为选出 $n$ 对数，恰好有 $i$ 对是 $a_i>b_j$ 对的方案数。

$g_i=f_{n,i}\times (n-i)!-\sum\limits^n_{j=1}g_j\tbinom{i}{j}$

输出 $g_{(n+k)/2}$。

这题代码是赛后写的，听说这题是个叫二项式反演的东西？

代码

#include <cstdio>
#include <algorithm>
#define int long long

inline int max(const int x, const int y) {return x > y ? x : y;}
const int mod = 1e9 + 9;
int f[2005][2005], g[2005], a[2005], b[2005], cnt[2005];
int fact[2005], inv[2005], n, k;

int qpow(int a, int b) {
	int ret = 1LL;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
int C(int n, int m) {
	return fact[n] * inv[n - m] % mod * inv[m] % mod;
}

signed main() {
	scanf("%lld%lld", &n, &k);
	fact[0] = 1LL;
	for (int i = 1; i <= 2000; ++ i)
		fact[i] = fact[i - 1] * i % mod;
	inv[2000] = qpow(fact[2000], mod - 2);
	for (int i = 1999; i >= 0; -- i)
		inv[i] = inv[i + 1] * (i + 1) % mod;
	for (int i = 1; i <= n; ++ i) scanf("%lld", a + i);
	for (int i = 1; i <= n; ++ i) scanf("%lld", b + i);
	std::sort(a + 1, a + n + 1);
	std::sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= n; ++ j)
		if (a[i] > b[j]) ++ cnt[i];
	for (int i = 0; i <= n; ++ i) f[i][0] = 1LL;
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= n; ++ j)
		f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * max(cnt[i] - j + 1, 0)) % mod;
	for (int i = n; i >= 1; -- i) {
		g[i] = f[n][i] * fact[n - i] % mod;
		for (int j = i + 1; j <= n; ++ j)
			g[i] = (g[i] - g[j] * C(j, i) % mod + mod) % mod;
	}
	if (n + k & 1) putchar('0');
	else printf("%lld", (g[n + k >> 1] + mod) % mod);
	return 0;
}

zqs`s blog

5-23数论专练总结

$A$

$B$

$C$

$D$

$E$