第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学C组）_第十四届蓝桥杯填充c语言

---

试题 A: 求和

本题总分：$5$ 分

---

【问题描述】

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

【答案提交】

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

---

204634714038436

---

自然数列求和，$1+2+\cdots +n=\frac{n(n+1)}{2}$。

#include <stdio.h>

int main() {
    printf("%lld", 20230408 * (20230408 + 1ll) / 2);
}
1
2
3
4
5

或者迭代答案。

#include <stdio.h>

int main() {
    long long ans = 0;
    for (int i = 1; i <= 20230408; ++i)
        ans += i;
    printf("%lld", ans);
}
1
2
3
4
5
6
7
8

---

试题 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 <stdio.h>
#include <time.h>
#include <queue>

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

试题 C: 三国游

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

---

【问题描述】

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

【输入格式】

  输入的第一行包含一个整数 $n$。
  第二行包含 $n$ 个整数表示 $A_i$，相邻整数之间使用一个空格分隔。
  第三行包含 $n$ 个整数表示 $B_i$，相邻整数之间使用一个空格分隔。
  第四行包含 $n$ 个整数表示 $C_i$，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

3
1 2 2
2 3 2
1 0 7
1
2
3
4

【样例输出】

2
1

【样例说明】

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

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 500$；
  对于 $70\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$1\le n\le 10^5，1\le A_i,B_i,C_i\le 10^9$。

---

贪心

---

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

#include <stdio.h>
#include <algorithm>

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; })
            )));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

22岁，喜欢屎山代码。

---

试题 D: 填充

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

---

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

1110?0
1

【样例输出】

2
1

【样例说明】

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

【评测用例规模与约定】

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

---

贪心

---

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

#include <stdio.h>

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

好像又把代码写成一坨了

---

试题 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$ 组数据的 $T_i$，第 $2i$ 行为第 $i$ 组数据的 $S_i$，$S_i$ 和 $T_i$ 长度均为 $n_i$。

【输出格式】

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

【样例输入】

2
1000111
1010101
01000
11000
1
2
3
4
5

【样例输出】

2
-1
1
2

【评测用例规模与约定】

  对于 $20\%$ 的评测用例，$1\le {\sum }_1^{{}_D}{n}_i\le 10$；
  对于所有评测用例，保证 $1\le {\sum }_1^{{}_D}{n}_i\le 10^6，n_i>0$。

---

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

#include <stdio.h>

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

试题 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}$。

【输出格式】

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

【样例输入】

2 3 1 2
1 2 3
4 5 6
1
2
3

【样例输出】

58
1

【样例说明】

  $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\le a\le n\le 10001\le b\le m\le 10001\le A_{i,j}\le 10^9$。

---

通过单调队列，先将矩阵(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 <stdio.h>

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

---

试题 G: 互质数的个数

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

---

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入 1】

2 5
1

【样例输出 1】

16
1

【样例输入 2】

12 7
1

【样例输出 2】

11943936
1

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$a,b\le 10^6$；
  对于 $70\%$ 的评测用例，$a\le 10^6，b\le 10^9$；
  对于所有评测用例，$1\le a\le 10^9，1\le b\le 10^{18}$。

---

题意就是求欧拉函数$\phi (a^b)$，由算术基本定理可知$n=p_1^{a_1}{p}_2^{a_2}\cdots p_s^{a_s}$， φ ( n ) = ∏ i = 1 s φ ( p i a i ) = ∏ i = 1 s p i a i − 1 ( p i − 1 ) = ∏ i = 1 s p i a i ( 1 − 1 p i ) = p 1 a 1 p 2 a 2 ⋯ p s a s ∏ i = 1 s ( 1 − 1 p i ) = n ∏ i = 1 s ( 1 − 1 p i )

$$\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$与$a^b$，显然它们的${\prod }_{i=1}^s(1-\frac{1}{p_i})$部分相等，即本质不同质因数没有变化，故答案为$a^{b-1}\phi (a)$。

#include <stdio.h>

#define MOD 998244353

long 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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

---

试题 H: 异或和之差

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

---

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

6
1 2 4 9 2 7
1
2

【样例输出】

14
1

【样例说明】

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

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$2\le n\le 2\times 10^5，0\le A_i\le 2^{20}$。

---

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

#include <stdio.h>
#include <algorithm>

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

---

试题  I: 公因数匹配

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

---

【问题描述】

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

【输入格式】

  输入的第一行包含一个整数 $n$。
  第二行包含 $n$ 个整数分别表示 $A_1{A}_2\cdots A_n$，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

5
5 3 2 6 9
1
2

【样例输出】

2 4
1

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$1\le n\le 10^5，1\le A_i\le 10^6$。

---

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

#include <stdio.h>
#include <vector>

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);
            else
                break;
        }
    }
    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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

试题 J: 子树的大小

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

---

【问题描述】

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

  

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

【输入格式】

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

【输出格式】

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

【样例输入】

3
1 2 1
11 3 4
74 5 3
1
2
3
4

【样例输出】

1
2
24
1
2
3

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$T\le 50，n\le 10^6，m\le 16$；
  对于所有评测用例，$1\le T\le 10^5，1\le k\le n\le 10^9，2\le m\le 10^9$。

---

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

#include <stdio.h>
#include <algorithm>

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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