I题

题解

把 $L$ 和 $R$ 的高 $\dfrac{n}{2}$ 位计作 $L_{1}$ 和 $R_{1}$，把低 $\dfrac{n}{2}$ 位计作 $L_{2}$ 和 $R_{2}$。大概的思路即为统计 $[L_{1}, R_{1}]$ 和 $[L_{2}, R_{2}]$ 分别有多少个平方数，处理一些细节并组合起来即可。这道题数字还蛮大，用python来实现更简单一点。

代码

from math import sqrt, isqrt
 
 
def count_square(l, r):
    if (l > r):
        return 0
 
    l = int(l)
    r = int(r)
    ans = isqrt(r) - isqrt(l)
    if (isqrt(l) * isqrt(l) == l):
        ans = ans + 1
    return ans
 
 
# 读取 n
n = int(input(""))
 
# 读取两个字符串
str1, str2 = input().split()
 
mid_index = n // 2
 
# 取出字符串的高 n/2 位和第 n/2 位
high_str1 = str1[:mid_index]
low_str1 = str1[mid_index:]
 
high_str2 = str2[:mid_index]
low_str2 = str2[mid_index:]
 
# 转化为整数
l1 = int(high_str1)
r1 = int(low_str1)
 
l2 = int(high_str2)
r2 = int(low_str2)
 
cnt1 = count_square(l1 + 1, l2 - 1)
cnt2 = count_square(0, 10 ** (n//2) - 1)
 
ans = cnt1 * cnt2
 
 
if (isqrt(l1) * isqrt(l1) == l1):
    ans += count_square(r1, 10 ** (n//2) - 1)
 
if (l1 != l2):
    if (isqrt(l2) * isqrt(l2) == l2):
        ans += count_square(0, r2)
 
print("%d" % ans)

K题

题目描述

题解

当 k != 1时，对单个个体来讲，先进行操作 2 一定优于先进行操作 1。而只有一直对最大的数进行操作 2，才能减少进行操作 1 的次数。所以我们不断对最大的数进行操作 2（即枚举操作 2 的次数），并更新答案即可。

代码

#include<bits/stdc++.h>
#define For(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define FOR(i, a, b) for(int (i) = (a); (i) >= (b); (i)--)
#define acl() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fix(i) cout << fixed << setprecision(i)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
constexpr int maxn = 1e6 + 10;
int main()
{
    int n, k, ans = 0, cnt = 0;
    priority_queue<int> Q;
    cin >> n >> k;
    vector<int> a(n + 1);
    For(i, 1, n) {
        cin >> a[i];
        Q.push(a[i]);
        ans = max(ans, a[i]);
    }
    if(k == 1){
        cout << ans;
        return 0;
    }       
    while(!Q.empty())
    {
        int t = Q.top(); Q.pop();
        if(t == 0) break;
        cnt ++;
        Q.push(t / k);
        ans = min(ans, Q.top() + cnt);
    }
    cout << ans;
    return 0;
}

C题

题解

这个题解改编自 cls。

首先我们证明：$\sum_{d \mid n} \varphi(d)=n$。

我们考虑 $\dfrac{1}{n}, \dfrac{2}{n}, \dots ,\dfrac{n}{n}$ 这 $n$ 个分数，可以看出这 $n$ 个分数一定可以被约分成 $\dfrac{k}{d}$ 的形式，其中 $d \mid n$ 且 $\gcd(k, d) = 1$。所以我们可以得到 $\sum_{d \mid n} \varphi(d) \geq n$。且对于每一个 $\dfrac{k}{d}$，一定可以化成 $\dfrac{k \cdot \dfrac{n}{d}}{n}$，所以 $\sum_{d \mid n} \varphi(d) \leq n$。故 $\sum_{d \mid n} \varphi(d)=n$。

其次我们证明：$\operatorname{gcd}(i, j)=\sum_{d|i, d| j} \varphi(d)$

$d \mid i$ 且 $d \mid j$ 等价于 $d \mid \gcd(i,j)$。令 $d^{\prime} = \gcd(i,j)$，则 $\sum_{d|i, d| j} \varphi(d) = \sum_{d | d^{\prime}} \varphi(d) = d^{\prime} = \gcd(i, j)$。

我们将答案分解为每个 $d$ 产生的贡献之和。考虑每个 $d$ 会出现的次数，在 $n$ 的范围内，$d$ 的倍数只会有 $\lfloor \frac{n}{d} \rfloor$个，因此所有的 $\gcd(i,j)$ 中，涉及到 $d$ 的有 $\lfloor \frac{n}{d} \rfloor^{2}$ 个

所以初始时，

$$ \sum_{i=1}^n \sum_{j=1}^n \operatorname{gcd}(i, j)=\sum_d \varphi(d) \cdot\left\lfloor\frac{n}{d}\right\rfloor^2=\sum_{d=1}^n \varphi(d) \cdot\left\lfloor\frac{n}{d}\right\rfloor^2 $$

因此可以定义 $M_d=\left\lfloor\frac{n}{d}\right\rfloor \times\left\lfloor\frac{n}{d}\right\rfloor$ 的矩阵 $(1 \leq d \leq n)$ ，每个元素都是 $\varphi(d)$ ，其中第 $(i, j)$ 位置的元素对应的是 $d$ 对 它的的第 $i$ 个倍数和第 $j$ 个倍数的贡献。

下面考虑每次操作的影响。我们先只考虑行操作，每次对 $x$ 行进行行操作会将 $\gcd(x,j)$ 变为 $y \cdot \gcd(x, j)$。

这个操作等价于对所有 $d \mid x$ 和 $d \mid j$ 的 $d$ ，将其矩阵 $M_{d}$ 的 $(\dfrac{x}{d}, \dfrac{j}{d})$ 这个元素变为原来的 y 倍。含义即是 $d$ 对第 $\dfrac{x}{d}$ 和第 $\dfrac{j}{d}$ 个倍数的贡献变为 y 倍。

而对应一个确定的 d，因为 $j$ 取遍 1 到 $n$, 或者说 1 到 $d, 2d, \dots, \lfloor\frac{n}{d}\rfloor d$，则 $M_{d}$ 的第 $\dfrac{x}{d}$ 行都变为原来的 y 倍。

或者再换句话说，这个操作等价于，对于 $x$ 的每个因数 $d$ ，将 $M_d$ 的第 $\frac{x}{d}$ 行乘 $y$。列操作也同理。

因此，每次操作 $x$ 行的所有数乘以 $y$ 可以通过记录每个 $d$ 的贡献来维护，即 $M_d$ 中的第 $x$ 行的值变成 $y$ 倍。对于列操作同理，具体的只需要记录 $M_d$ 中的第 $x$ 行或者第 $y$ 列最终变成多少倍 $r_i, c_i$, 那么对于每个 $d$ ，最终的贡献就是 $\varphi(d) \cdot\left(\sum r_i\right) \cdot\left(\sum c_i\right)$ 。于是最终答案就是 $$ \sum_{d=1}^n\left(\varphi(d) \cdot\left(\sum r_i\right) \cdot\left(\sum c_i\right)\right) $$