线性筛 + 枚举#

时间复杂度 $O(n + T\frac{n}{ln n})$

首先用线性筛求出所有的素数，然后枚举所有素数，看是否是 $n$ 的约数

代码如下

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 100010;
7

8
int p[N], cnt = 0;
9
bool st[N];
10

11
void init(int n) {
12

13
    for (int i = 2; i <= n; i ++ ) {
14
        if (!st[i]) p[cnt ++ ] = i;
15
        for (int j = 0; i <= n / p[j]; j ++ ) {
16
            st[i * p[j]] = true;
17
            if (i % p[j] == 0) break;
18
        }
19
    }
20
}
21

22
void solve() {
23
    int n; scanf("%d", &n);
24
  //  cout << cnt << endl;
25
    for (int i = 0; p[i] <= n; i ++ )
26
        if (n % p[i] == 0) {
27
            printf("%d\n", p[i]);
28
            break;
29
        }
30
}
31

32
int main() {
33

34
    // freopen("in.txt", "r", stdin);
35
    // freopen("out.txt", "w", stdout);
36

37
    init(N - 1);
38
    int T; scanf("%d", &T);
39
    while (T -- ) {
40
        solve();
41
    }
42
}

TIP

hh，事实上线性筛本质上就是用一个合数的最小素数因数将该合数筛掉，因此只需要保存每个数的最小素数因子即可。所以最后的枚举多此一举，时间复杂度应该为 $O(n+T)$

思维#

时间复杂度 $O(nlogn)$

可以想象这个数组极差最小是多少？一定是 $0$ 或者 $1$

假设此时极差不为 $0$ 或者 $1$，也就是最大值 $a_{max}$ 和最小值 $a_{min}$ 之差 $\ge 2$ ，那么此时可以通过一次操作将这两个数的差降到 $0$ 或者 $1$。如果进行了此次调整，极差仍然不为 $0$ 或者 $1$，继续执行改步骤即可

另外，假设 $S = \sum a_i$ ，由于每次操作都有一个数减一，一个数加一，因此每次操作 $S$ 不变。

因此，如果 $S \% n = 0$，说明最后极差一定为 $0$，且每个数都为 $S / n$；如果 $S \% n \neq 0$，说明最后极差一定为 $1$，且有 $S \% n$ 个数为 $\frac{S}{n} + 1$ ，$n - S \% n$ 个数为 $S / n$

根据贪心性质，将数组从大到小排序，前面 $S \% n$ 个数变成 $\frac{S}{n} + 1$ 和后面的$n - S \% n$ 个数变成 $S / n$ 需要操作数为 $res$

最终答案就是 $res / 2$

代码如下

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4

5
using namespace std;
6

7
typedef long long LL;
8

9
const int N = 100010;
10

11
int q[N];
12
int n;
13

14
int main() {
15

16
    // freopen("in.txt", "r", stdin);
17
    // freopen("out.txt", "w", stdout);
18

19

20
    scanf("%d", &n);
21
    LL sum = 0;
22
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]), sum += q[i];
23
    sort(q, q + n);
24
    reverse(q, q + n);
25
    LL t1 = sum / n, t2 = sum % n;
26

27
    LL res = 0;
28
    for (int i = 0; i < n; i ++ )
29
        if (i < t2) res += abs(q[i] - t1 - 1);
30
        else res += abs(q[i] - t1);
31
    printf("%lld\n", res / 2);
32

33
}

CAUTION

注意开 long long

WARNING

下题暂未给出代码，仅给出目前思路，等 A 了之后再上传

暴力#

时间复杂度 $O(n^3)$

根据上述分析，有一个很暴力的解法就是枚举小红选择的区间，然后小明对每个修改后的数组求一遍最大或者最小子段和，然后所有区间能求得的最大值就是 $sum$

线段树优化#

---Update: 2024-08-28

IMPORTANT

hh，这题事实上线段树就解决了，下面的分析完全不需要。 暴力枚举小红的区间，然后每个区间乘 $k$，线段树可以 $logn$ 更新；然后求最大/小连续子区间也可以线段树求。

数据结构太弱了 ~

时间复杂度 $O(n^2 logn)$

首先先把特殊情况去掉，如果 $k = 1$ ，则无论怎么样，$sum$ 的值都不会变，因此情况分为 $k > 1$ 和 $k < 1$；以下分析只考虑 $k > 1$ 的情况， $k < 1$ 的分析类似。

上面这个暴力的时间复杂度问题在于枚举了小红选择的所有区间，并且小红和小明最后所选的区间也没有任何联系，那么能否优化这部分？

答案是肯定的。我们仔细想一想，小红和小明选择的区间是否存在交叉的情况

TIP

区间A: [1,5]，区间B:[2,6]。区间 A B 表示交叉，如果 A 完全包含 B 或者 B 完全包含 A，不表示交叉；同时，A 和 B 没有交集也表示不交叉。

假设最后选择中，小红和小明选择的区间是由交叉部分的，如果交叉部分的和的值是等于 0 的，无论是小红还是小明，加上这个区间都没有意义，相当于两人的选择是没有交集的；如果交叉部分的和的值是大于 0 的，那么对于小明来说，不选择这个区间比选择这个区间更优，因此可以去掉这个区间；如果交叉部分的和的值是小于 0 的，那么对于小红来说，这部分区间反而给小明利用了，因此不选择这部分区间比选择这部分区间更优

综上，小红小明最终选择的两区间，一定是不交叉的。（注意可以是包含关系）

因此这里分为三种情况考虑：

假设同样枚举小红区间为 $[l,r]$

1. 小红与小明区间没有交集

   小明则无非是选择 $[1,l-1]$ 或者 $[r + 1, n]$ 的最小子段和

2. 小明区间完全包含小红区间

   小明无非就是选择以 $[1,l-1]$ 中以 $l-1$ 为终点的最小子段和的区间以及 $[r + 1, n]$ 中以 r + 1 为起点的最小子段和的区间以及 $[l,r]$

3. 小红区间完全包含小明区间

   $[l,r]$ 区间的最小字段和

可以看到上述 1、2 好求，但是 3 目前只能想到用线段树来维护，因此每次求这个区间最小字段和的时间复杂度为 $O(logn)$

写在最后，第三题有更好的解法欢迎讨论