第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学C组）

蓝桥杯 2023年省赛真题
^{C/C++ 大学C组}

• 试题 A: 求和
• 试题 B: 工作时长
• 试题 C: 三国游
• 试题 D: 填充
• 试题 E: 翻转
• 试题 F: 子矩阵
• 试题 G: 互质数的个数
• 试题 H: 异或和之差
• 试题 I: 公因数匹配
• 试题 J: 子树的大小

试题 A: 求和

本题总分：$5$ 分

【问题描述】

  求 $1$ （含）至 $20230408$ （含）中每个数的和。

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

204634714038436

自然数列求和， 1 + 2 + ⋯ + n =n(n+1)2 1+2+\cdots+n=\cfrac {n(n+1)}21+2+⋯+n=2n(n+1)​。

#include int main() {printf("%lld", 20230408 * (20230408 + 1ll) / 2);}

或者迭代答案。

#include int main() {long long ans = 0;for (int i = 1; i <= 20230408; ++i)ans += i;printf("%lld", ans);}

试题 B: 工作时长

本题总分：$5$ 分

【问题描述】

  小蓝手里有一份 2022 年度自己的上班打卡记录文件，文件包含若干条打卡记录，每条记录的格式均为 “$\mathrm{yyyy}$–$\mathrm{MM}$–$\mathrm{dd}\mathrm{HH}:\mathrm{mm}:\mathrm{ss}$”，即按照年 -月 -日时:分: 秒的形式记录着一个时间点 (采用 $24$ 小时进制)。由于某些原因，这份文件中的时间记录并不是按照打卡的时间顺序记录的，而是被打乱了。但我们保证小蓝每次上班和下班时都会正常打卡，而且正好打卡一次，其它时候不会打卡。每一对相邻的上 -下班打卡之间的时间就是小蓝本次的工作时长，例如文件内容如下的话：

$2022$–$01$–$0112:00:05$
$2022$–$01$–$0200:20:05$
$2022$–$01$–$0107:58:02$
$2022$–$01$–$0116:01:35$

表示文件中共包含了两段上下班记录，$1）2022$–$01$–$0107:58:02\sim 2022$–$01$–$0112:00:05$，工作时长为 $14523$ 秒；$2）2022$–$01$–$0116:01:35\sim 2022$–$01$–$0200:20:05$ 工作时长为 $29910$ 秒；工作时长一共是 $14523+29910=44433$ 秒。现在小蓝想知道在 $2022$ 年度自己的工作时长一共是多少秒？

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

unknow

没数据，写个差不多的程序意思一下。

#include #include #include int main() {freopen("lock-in.all.txt", "r", stdin);std::priority_queue<clock_t> pq;for (tm tm; ~scanf("%d-%d-%d %d:%d:%d", &tm.tm_year, &tm.tm_mon, &tm.tm_mday, &tm.tm_hour, &tm.tm_min, &tm.tm_sec);)tm.tm_year -= 1900, --tm.tm_mon, pq.push(mktime(&tm));long long cnt = 0;for (int sign = 1; pq.size(); sign = -sign)cnt += sign * pq.top(), pq.pop();printf("%lld", cnt);}

试题 C: 三国游

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$10$ 分

【问题描述】

  小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 $X,Y,Z$ (一开始可以认为都为 $0$ )。游戏有 $n$ 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 $i$ 个事件发生时会分别让 $X,Y,Z$ 增加 Ai, Bi, Ci A_i, B_i,C_iAi​,Bi​,Ci​。
 当游戏结束时 (所有事件的发生与否已经确定)，如果 $X,Y,Z$ 的其中一个大于另外两个之和，我们认为其获胜。例如，当 $X>Y+Z$ 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
 如果不存在任何能让某国获胜的情况，请输出 $-1$。

【输入格式】

  输入的第一行包含一个整数 $n$。
 第二行包含 $n$ 个整数表示 Ai A_iAi​，相邻整数之间使用一个空格分隔。
 第三行包含 $n$ 个整数表示 Bi B_iBi​，相邻整数之间使用一个空格分隔。
 第四行包含 $n$ 个整数表示 Ci C_iCi​，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

31 2 22 3 21 0 7

【样例输出】

2

【样例说明】

  发生两个事件时，有两种不同的情况会出现获胜方。
 发生 $1,2$ 事件时蜀国获胜。
 发生 $1,3$ 事件时吴国获胜。

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 500$；
 对于 $70\%$ 的评测用例，$n\le 5000$；
 对于所有评测用例， 1 ≤ n ≤ 1 05， 1 ≤ Ai, Bi, Ci≤ 1 09 1 ≤ n ≤ 10^5，1 ≤ A_i, B_i,C_i ≤ 10^91≤n≤105，1≤Ai​,Bi​,Ci​≤109。

贪心

同时考虑三个国家是相当困难的，于是考虑分别求出魏蜀吴分别获胜的话最大事件数，最优答案就是这若干个数中的最大值。
以魏举例，记第 $i$ 个事件对魏获胜的贡献为 xi− yi− zi x_i -y_i -z_ixi​−yi​−zi​，按贡献降序重排事件，找到一个 $k$，满足 ∑ i = 1kxi> ∑ i = 1k( yi+ zi)\sum_{i=1}^kx_i >\sum_{i=1}^k(y_i + z_i)∑i=1k​xi​>∑i=1k​(yi​+zi​) 且 $k$ 尽可能大，若 $k<n$，易知 ∑ i = 1 k + 1xi≤ ∑ i = 1 k + 1( yi+ zi)\sum_{i=1}^{k+1}x_i \leq\sum_{i=1}^{k+1}(y_i + z_i)∑i=1k+1​xi​≤∑i=1k+1​(yi​+zi​) 且 $[1,k]$ 间的或 $(k,n]$ 间的事件交换不会对和式值造成影响，$[1,k]$ 间与 $(k,n]$ 间的元素交换会使 ∑ i = 1 k + 1( xi− yi− zi)\sum_{i=1}^{k+1}(x_i-y_i – z_i)∑i=1k+1​(xi​−yi​−zi​) 变小，不等式无法成立，从而 k 对魏来说最优。

#include #include struct tuple {int x, y, z;} xyz[100000];int n;int greedy(bool cmp(tuple, tuple), bool check(long long, long long, long long)) {std::sort(xyz, xyz + n, cmp);long long x = 0, y = 0, z = 0;int res = -2;for (int i = 0; i < n; ++i) {x += xyz[i].x;y += xyz[i].y;z += xyz[i].z;if (check(x, y ,z)) res = i;}return res + 1;}int main() {scanf("%d", &n);for (int i = 0; i < n; ++i) scanf("%d", &xyz[i].x);for (int i = 0; i < n; ++i) scanf("%d", &xyz[i].y);for (int i = 0; i < n; ++i) scanf("%d", &xyz[i].z);printf("%d", std::max(greedy([](tuple a, tuple b)-> bool { return a.x - a.y - a.z > b.x - b.y - b.z; }, [](long long x, long long y, long long z) -> bool { return x > y + z; }), std::max(greedy([](tuple a, tuple b)-> bool { return a.y - a.x - a.z > b.y - b.x - b.z; }, [](long long x, long long y, long long z) -> bool { return y > x + z; }),greedy([](tuple a, tuple b)-> bool { return a.z - a.x - a.y > b.z - b.x - b.y; }, [](long long x, long long y, long long z) -> bool { return z > x + y; }))));}

22岁，喜欢屎山代码。

试题 D: 填充

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$10$ 分

【问题描述】

  有一个长度为 $n$ 的 $01$ 串，其中有一些位置标记为 $?$，这些位置上可以任意填充 $0$ 或者 $1$，请问如何填充这些位置使得这个 $01$ 串中出现互不重叠的 $00$ 和 $11$ 子串最多，输出子串个数。

【输入格式】

  输入一行包含一个字符串。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

1110?0

【样例输出】

2

【样例说明】

  如果在问号处填 $0$，则最多出现一个 $00$ 和一个 $11：111000$。

【评测用例规模与约定】

  对于所有评测用例，$1\le n\le 1000000$。

贪心

如果以01相接的地方为断点，将01串拆分开来，如1110?0拆分成111、0?0，则显然第二段中的问号应填0，于是只需考虑若干问号存在01之间的情况，如果若干问号的左侧段长为奇数，则考虑将一个问号变为左侧段对应的值，使总答案加一，然后将所有问号变为右侧段对应的值，若剩余问号为奇数则这个数字除二向下取整是雷打不动的，而多余的一个变为左侧对答案无贡献，所以直接变右，这么模拟着递推过来就行。
实现时连续的问号同时当做0、1来看待，然后找到子串后清空累计即可。

#include int ans, cnt['1' + 1];char buf[1000010];int main() {gets(buf);for (int i = 0; buf[i]; ++i) {if (buf[i] == '?') {if (cnt['0']) ++cnt['0'];else if (cnt['1']) ++cnt['1'];else ++cnt['0'], ++cnt['1'];} else ++cnt[buf[i]], cnt[buf[i] ^ 1] = 0;if (cnt['0'] == 2 || cnt['1'] == 2)++ans, cnt['0'] = cnt['1'] = 0;}printf("%d", ans);}

好像又把代码写成一坨了

试题 E: 翻转

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$15$ 分

【问题描述】

  小蓝用黑白棋的 $n$ 个棋子排成了一行，他在脑海里想象出了一个长度为 $n$ 的 $01$ 串 $T$，他发现如果把黑棋当做 $1$，白棋当做 $0$，这一行棋子也是一个长度为 $n$ 的 $01$ 串 $S$。
 小蓝决定，如果在 $S$ 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 $S$ 中存在子串 $101$ 或者 $010$，就可以选择将其分别变为 $111$ 和 $000$，这样的操作可以无限重复。
 小蓝想知道最少翻转多少次可以把 $S$ 变成和 $T$ 一模一样。

【输入格式】

  输入包含多组数据。
 输入的第一行包含一个正整数 $D$ 表示数据组数。
 后面 $2D$ 行每行包含一个 $01$ 串，每两行为一组数据，第 $2i-1$ 行为第 $i$ 组数据的 Ti T_iTi​，第 $2i$ 行为第 $i$ 组数据的 Si S_iSi​， Si S_iSi​ 和 Ti T_iTi​ 长度均为 ni n_ini​。

【输出格式】

  对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 −1。

【样例输入】

2100011110101010100011000

【样例输出】

2-1

【评测用例规模与约定】

  对于 $20\%$ 的评测用例， 1 ≤ ∑1 Dni≤ 101 ≤\sum_1^{{}_D} n_i ≤ 101≤∑1D​​ni​≤10；
 对于所有评测用例，保证 1 ≤ ∑1 Dni≤ 1 06， ni> 01 ≤\sum_1^{{}_D} n_i ≤ 10^6 ，n_i > 01≤∑1D​​ni​≤106，ni​>0。

由题意可知，端点棋子是无法翻转的，而当某一个棋子翻转时，它与相邻棋子连续相同，故无法产生新的翻转点，因此端点特判然后遍历模拟就行。

#include char T[1000010], S[1000010];int D, cnt;int main() {for (scanf("%d\n", &D); gets(T + 1), gets(S + 1), D--;) {for (int i = 1; S[i]; ++i) {if (S[i] == T[i]) continue;if (S[i - 1] == S[i] ^ 1 && S[i - 1] == S[i + 1]) S[i] ^= 1, ++cnt;else {cnt = -1;break;}}printf("%d\n", cnt), cnt = 0;}}

试题 F: 子矩阵

时间限制: $2.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$15$ 分

【问题描述】

  给定一个 $n\times m$ （$n$ 行 $m$ 列）的矩阵。
 设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 $a\times b$ （$a$ 行 $b$ 列）的子矩阵的价值的和。
 答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

【输入格式】

  输入的第一行包含四个整数分别表示 $n,m,a,b$，相邻整数之间使用一个空格分隔。
 接下来 $n$ 行每行包含 $m$ 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 A i , j A_{i, j}Ai,j​。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

2 3 1 21 2 34 5 6

【样例输出】

58

【样例说明】

  $1\times 2+2\times 3+4\times 5+5\times 6=58$。

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$1\le n,m\le 100$；
 对于 $70\%$ 的评测用例，$1\le n,m\le 500$；
 对于所有评测用例， 1 ≤ a ≤ n ≤ 10001 ≤ b ≤ m ≤ 10001 ≤ A i , j≤ 1 09 1 ≤ a ≤ n ≤ 1000\ 1 ≤ b ≤ m ≤ 1000\ 1 ≤ A_{i, j} ≤ 10^91≤a≤n≤10001≤b≤m≤10001≤Ai,j​≤109。

通过单调队列，先将矩阵(i-a+1,j)(i,j)的最值求出，然后如法炮制求出(i-a+1,j-b+1)(i,j-b+1)、(i-a+1,j-b+2)(i,j-b+2)、…、(i-a+1,j)(i,j)的最值，即(i-a+1,j-b+1)(i,j)的最值。
单调队列求最值懒得讲了，关键字：单调队列、滑动窗口、区间最值，自己搜着看吧。

#include int n, m, a, b, maxh, maxt, minh, mint, max[1000][1000], min[1000][1000], maxq[1010], minq[1010];int main() {scanf("%d %d %d %d", &n, &m, &a, &b);for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j)scanf("%d", &max[i][j]);for (int j = m - 1; ~j; --j) {maxh = maxt = minh = mint = 0;for (int i = 1; i <= a; ++i) {while (maxh != maxt && max[n - i][j] >= max[maxq[maxt - 1]][j]) --maxt;while (minh != mint && max[n - i][j] <= max[minq[mint - 1]][j]) --mint;maxq[maxt++] = n - i;minq[mint++] = n - i;}for (int i = n - 1; ~i; --i) {while (maxh != maxt && maxq[maxh] > i) ++maxh;while (minh != mint && minq[minh] > i) ++minh;min[i][j] = max[minq[minh]][j];max[i][j] = max[maxq[maxh]][j];if (i - a >= 0) {while (maxh != maxt && max[i - a][j] >= max[maxq[maxt - 1]][j]) --maxt;while (minh != mint && max[i - a][j] <= max[minq[mint - 1]][j]) --mint;maxq[maxt++] = i - a;minq[mint++] = i - a;}}}long long ans = 0;for (int i = 0; i < n; ++i) {maxh = maxt = minh = mint = 0;for (int j = 0; j < m; ++j) {while (maxh != maxt && maxq[maxh] <= j - b) ++maxh;while (minh != mint && minq[minh] <= j - b) ++minh;while (maxh != maxt && max[i][j] >= max[i][maxq[maxt - 1]]) --maxt;while (minh != mint && min[i][j] <= min[i][minq[mint - 1]]) --mint;maxq[maxt++] = j;minq[mint++] = j;if (i >= a - 1 && j >= b - 1)ans = (ans + 1ll * max[i][maxq[maxh]] * min[i][minq[minh]]) % 998244353;}}printf("%lld", ans);}

省了个保存原数组的空间开销，代码一坨

试题 G: 互质数的个数

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$20$ 分

【问题描述】

  给定 $a,b$，求 1 ≤ x < ab 1 ≤ x < a^b1≤x<ab 中有多少个 $x$ 与 ab a^bab 互质。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

【输入格式】

  输入一行包含两个整数分别表示 $a,b$，用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入 1】

2 5

【样例输出 1】

16

【样例输入 2】

12 7

【样例输出 2】

11943936

【评测用例规模与约定】

  对于 $30\%$ 的评测用例， a , b ≤ 1 06 a,b ≤ 10^6a,b≤106；
 对于 $70\%$ 的评测用例， a ≤ 1 06， b ≤ 1 09 a ≤ 10^6，b ≤ 10^9a≤106，b≤109；
 对于所有评测用例， 1 ≤ a ≤ 1 09， 1 ≤ b ≤ 1 018 1 ≤ a ≤ 10^9，1 ≤ b ≤ 10^{18}1≤a≤109，1≤b≤1018。

题意就是求欧拉函数 φ ( ab)\varphi(a^b)φ(ab)，由算术基本定理可知 n = p1 a 1p2 a 2⋯ ps a s n=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}n=p1a1​​p2a2​​⋯psas​​，φ(n) = ∏ i=1sφ( p i ai ) = ∏ i=1s p ia i−1 ( p i−1) = ∏ i=1s p i ai (1− 1 pi ) = p 1 a1p 2 a2 ⋯ p s as∏ i=1s(1− 1 pi ) =n ∏ i=1s(1− 1 pi )\begin{split} \varphi(n) &=\prod_{i=1}^s\varphi(p_i^{a_i})\\ &=\prod_{i=1}^sp_i^{a_i-1}(p_i-1)\\ &=\prod_{i=1}^sp_i^{a_i}(1-\frac 1{p_i})\\ &=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}\prod_{i=1}^s(1-\frac 1{p_i})\\ &=n\prod_{i=1}^s(1-\frac 1{p_i}) \end{split} φ(n)​=i=1∏s​φ(piai​​)=i=1∏s​piai​−1​(pi​−1)=i=1∏s​piai​​(1−pi​1​)=p1a1​​p2a2​​⋯psas​​i=1∏s​(1−pi​1​)=ni=1∏s​(1−pi​1​)​而对于$a$与 ab a^bab，显然它们的 ∏ i = 1s( 1 − 1 p i)\prod_{i=1}^s(1-\frac 1{p_i})∏i=1s​(1−pi​1​)部分相等，即本质不同质因数没有变化，故答案为 a b − 1φ ( a )a^{b-1}\varphi(a)ab−1φ(a)。

#include #define MOD 998244353long long qpow(long long a, long long b) {a %= MOD;long long p = 1;for (; b > 0; b >>= 1) {if (b & 1) p = p * a % MOD;a = a * a % MOD;}return p;}long long a, b, ans;int main() {scanf("%d %lld", &a, &b);ans = qpow(a, b);for (int p = 2; p * p <= a; ++p) {if (a % p == 0) {ans = ((ans * qpow(p, MOD - 2)) % MOD) * (p - 1) % MOD;while (a % p == 0) a /= p;}}if (a > 1) ans = ((ans * qpow(a, MOD - 2)) % MOD) * (a - 1) % MOD;printf("%lld", ans);}

截止2023年5月12日16:31:11，dotcpp上的民间数据有误，当$a$取 ab a^bab余数部分，并且$ans\nmid p$时才能通过所有用例，错的离谱，害得我de半天bug。

试题 H: 异或和之差

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$20$ 分

【问题描述】

  给定一个含有 $n$ 个元素的数组 Ai A_iAi​，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

【输入格式】

  输入的第一行包含一个整数 $n$ 。
 第二行包含 $n$ 个整数 Ai A_iAi​，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

61 2 4 9 2 7

【样例输出】

14

【样例说明】

  两个子段可以分别选 $1$ 和 $4，9，2$，差值为 $15-1=14$。

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
 对于所有评测用例， 2 ≤ n ≤ 2 × 1 05， 0 ≤ Ai≤ 220 2 ≤ n ≤ 2 × 10^5，0 ≤ A_i ≤ 2^{20}2≤n≤2×105，0≤Ai​≤220。

01字典树，里面存前缀异或和，然后查询[1,i][i,n]的最值，做个dp最后枚举答案。

#include #include int n, m = 20, ans, cur, a[200010], lmax, lmin, rmax[200010], rmin[200010], trie[800010][2];void add(int x) {int rt = 0;for (int i = m; ~i; --i) {int b = (x >> i) & 1;if (!trie[rt][b]) trie[rt][b] = ++cur;rt = trie[rt][b];}}int xor_max(int x) {int rt = 0, max = 0;for (int i = m; ~i; --i) {int b = (x >> i) & 1;if (trie[rt][b ^ 1]) {rt = trie[rt][b ^ 1];max |= 1 << i;} else rt = trie[rt][b];}return max;}int xor_min(int x) {int rt = 0, min = 0;for (int i = m; ~i; --i) {int b = (x >> i) & 1;if (trie[rt][b]) rt = trie[rt][b];else {rt = trie[rt][b ^ 1];min |= 1 << i;}}return min;}int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);lmin = rmin[n + 1] = 0x3f3f3f3f;for (int i = n, s = 0; i > 0; --i) {add(s), s ^= a[i];rmax[i] = std::max(rmax[i + 1], xor_max(s));rmin[i] = std::min(rmin[i + 1], xor_min(s));}for (; cur; --cur) trie[cur][0] = trie[cur][1] = 0;trie[0][1] = trie[0][0] = 0;for (int i = 1, s = 0; i < n; ++i) {add(s), s ^= a[i];lmax = std::max(lmax, xor_max(s));lmin = std::min(lmin, xor_min(s));ans = std::max(ans, lmax - rmin[i + 1]);ans = std::max(ans, rmax[i + 1] - lmin);}printf("%d", ans);}

试题 I: 公因数匹配

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$25$ 分

【问题描述】

  给定 $n$ 个正整数 Ai A_iAi​，请找出两个数 $i,j$ 使得 $i<j$ 且 Ai A_iAi​ 和 Aj A_jAj​ 存在大于 $1$ 的公因数。
 如果存在多组 $i,j$，请输出 $i$ 最小的那组。如果仍然存在多组 $i,j$，请输出 $i$ 最小的所有方案中 $j$ 最小的那组。

【输入格式】

  输入的第一行包含一个整数 $n$。
 第二行包含 $n$ 个整数分别表示 A1A2⋯ An A_1 A_2 \cdots A_nA1​A2​⋯An​，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含两个整数分别表示题目要求的 $i,j$，用一个空格分隔。

【样例输入】

55 3 2 6 9

【样例输出】

2 4

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
 对于所有评测用例， 1 ≤ n ≤ 1 05， 1 ≤ Ai≤ 1 06 1 ≤ n ≤ 10^5，1 ≤ A_i ≤ 10^61≤n≤105，1≤Ai​≤106。

欧拉筛计算出A范围内每个整数的本质不同质因数，易知 1 06 10^6106内整数本质不同质因数不会超过十个，从后往前遍历并记录每个因数最新一次出现位置，线性时间就能跑出来。

#include #include std::vector<int> primes, pfs[1000001];int n, a[100010], last[1000000];int main() {for (int i = 2; i <= 1000000; ++i) {if (pfs[i].empty()) {primes.push_back(i);pfs[i] = {i};}for (int p : primes) {if (p * i > 1000000) break;pfs[p * i] = pfs[i];if (p % i)pfs[p * i].push_back(p);elsebreak;}}scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);std::pair<int, int> ans = { 0x3f3f3f3f, 0 };for (int i = n; i; --i)for (int pf : pfs[a[i]]) {if (last[pf])ans = std::min(ans, {i, last[pf]});last[pf] = i;}printf("%d %d", ans.first, ans.second);}

试题 J: 子树的大小

时间限制: $2.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$25$ 分

【问题描述】

  给定一棵包含 $n$ 个结点的完全 $m$ 叉树，结点按从根到叶、从左到右的顺序依次编号。
 例如下图是一个拥有 $11$ 个结点的完全 $3$ 叉树。

  你需要求出第 $k$ 个结点对应的子树拥有的结点数量。

【输入格式】

  输入包含多组询问。
 输入的第一行包含一个整数 $T$ ，表示询问次数。
 接下来 $T$ 行，每行包含三个整数 $n,m,k$ 表示一组询问。

【输出格式】

  输出 $T$ 行，每行包含一个整数表示对应询问的答案。

【样例输入】

31 2 111 3 474 5 3

【样例输出】

1224

【评测用例规模与约定】

  对于 $40\%$ 的评测用例， T ≤ 50 ， n ≤ 1 06， m ≤ 16T ≤ 50，n ≤ 10^6，m ≤ 16T≤50，n≤106，m≤16；
 对于所有评测用例， 1 ≤ T ≤ 1 05， 1 ≤ k ≤ n ≤ 1 09， 2 ≤ m ≤ 1 09 1 ≤ T ≤ 10^5，1 ≤ k ≤ n ≤ 10^9，2 ≤ m ≤ 10^91≤T≤105，1≤k≤n≤109，2≤m≤109。

容易发现，高度同为$h$的节点编号连续，从 1 + ∑ i = 0 h − 1mi 1+\sum_{i=0}^{h-1}m^i1+∑i=0h−1​mi排到 ∑ i = 0hmi \sum_{i=0}^hm^i∑i=0h​mi，因此我们可以枚举每一层的编号然后统计是$k$的子节点的节点的个数，每次询问复杂度为 O (log ⁡mn )O(\log_mn)O(logm​n)。
对于那一段节点是$k$的子节点，我们记$k$所在的高度为$h$，$k$在兄弟节点中的排位为$r$，则$k+1$层是$k$子节点的节点的序号应落入 [ 1 + ∑ i = 0hmi+ ( r − 1 ) m1, 1 + ∑ i = 0hmi+ r m1)[1+\sum_{i=0}^{h}m^i+(r-1)m^1,1+\sum_{i=0}^{h}m^i+rm^1)[1+∑i=0h​mi+(r−1)m1,1+∑i=0h​mi+rm1)这个区间，对于$h+j$层容易找到关系式 [ 1 + ∑ i = 0 h + j − 1mi+ ( r − 1 ) mj, 1 + ∑ i = 0hmi+ r mj)[1+\sum_{i=0}^{h+j-1}m^i+(r-1)m^j,1+\sum_{i=0}^{h}m^i+rm^j)[1+∑i=0h+j−1​mi+(r−1)mj,1+∑i=0h​mi+rmj)，把模拟题藏成这样，欺负我专科兄弟是吧。

#include #include int main() {int _, n, m, k;for (scanf("%d", &_); _--;) {scanf("%d %d %d", &n, &m, &k);long long first = 0, last = 0, kf, kr, kl = 1, powm = 1;int ans = 1;while (first > k || last < k)first = last + 1, last = last + powm, powm *= m;kr = k - first;while (last < n) {first = last + 1, last = last + powm, powm *= m;kl *= m, kf = first + kr * kl;if (kf > n) break;ans += std::min(kf + kl - 1, (long long)n) - kf + 1;}printf("%d\n", ans);}}

也可以简化一点，将答案拆成最后一层和其余两部分，这样答案就是一个满$m$叉树节点个数加上上述方法求出的最后一层节点个数，这么写代码可能会显得更可读，大概。