CF1646E Power Board 题解

题目链接：https://codeforces.com/contest/1646/problem/E

题目大意：

有一个 \(n \times m\) 的矩阵，其中第 \(i\) 行第 \(j\) 列的格子中的数字是 \(i^j\)。
问：矩阵中存在多少个不同的数？

解题思路：

可以很明显地发现，第 \(1\) 行的数字全部都是 \(1\)，而且在其它行不会出现数值为 \(1\) 的数字。

我们称一个整数是 次方数 如果它它可以表示成 \(x^a\) 的形式，其中 \(x\) 和 \(a\) 都是正整数且 \(a \gt 1\)。对于一个不是次方数的正整数 \(x\)，我们定义 \(R(x)\) 表示整数 \(x, x^2, x^3, \ldots\) 的出现在矩阵中的数字对应的集合。

可以断言：如果存在两个整数 \(x\) 和 \(y\) 满足 \(x \neq y\) 且 \(x\) 和 \(y\) 均不是次方数，则 \(R(x)\) 和 \(R(y)\) 不包含相同的元素。
证明：假设存在相同的元素，那么也就说明存在两个正整数 \(a, b\) 满足 \(x^a = y^b\)，这等价于 \(x = y^{\frac{b}{a}}\)，由于 \(y\) 不是一个次方数，所以 \(\frac{b}{a}\) 不是一个整数。如果 \(\frac{b}{a} = 1\) 则 \(x = y\)，这也不可能发生。而 \(\frac{b}{a} \gt 1\) 也不可能发生，因为 \(x\) 不是一个次方数。所以：不会存在相同的元素。

基于上述结论，对于每一个非次方数 \(x\)，我们可以单独计算 \(R(x)\)。

对于一个整数 \(x\)，我们用 \(k\) 表示以 \(x\) 的幂开头的行数。则 \(R(x)\) 包含了所有满足 \(1 \le i \le k\) 且 \(1 \le j \le m\) 的 \(x^{i \cdot j}\)。然后，集合的大小就等价于存在多少个不同的 \(i \cdot j\) 满足 \(1 \le i \le k\) 且 \(1 \le j \le m\)。这也就是说，集合中的数字个数与 \(x\) 无关，而只与 \(k\) 有关。

因此，\(R(x)\) 的大小取决于 \(k\)。因为 \(x^k \le n\)，所以我们可以得到 \(k \le \log(n)\)。因为，对于每一个 \(k = 1, 2, \ldots, \lfloor \log(n) \rfloor\)，我们只需去计算一下存在多少个不同的整数 \(i \cdot j\) 满足 \(1 \le i \le k\) 且 \(1 \le j \le m\) 即可。我们可以使用一个长度为 \(m \cdot \log(n)\) 的数组，在第 \(i\) 步（对于 \(i = 1, 2, \ldots, \lfloor \log(n) \rfloor\)）我们标记数字 \(i, 2i, \ldots, mi\) 在数组中是访问过的，并且将没有访问过的标记为访问过然后加入到数组中即可。在第 \(i\) 步我们相当于计算了 \(k = i\) 的情况。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

bool vis[maxn * 20], vis2[maxn];
int n, m, cnt, sum[maxn];
long long ans;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= m; j++) {
            if (!vis[i * j]) {
                vis[i * j] = true;
                cnt++;
            }
        }
        sum[i] = cnt;
    }
    ans = 1;
    for (int i = 2; i <= n; i++) {
        if (vis2[i]) continue;
        long long x = i, k = 0;
        while (x <= n) {
            vis2[x] = true;
            k++;
            x *= i;
        }
        ans += sum[k];
    }
    cout << ans << endl;
    return 0;
}