题目链接: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;
}
标签:CF1646E,le,log,cdot,题解,int,Board,次方,ldots
From: https://www.cnblogs.com/quanjun/p/17326684.html