简单题，但是没想出来
考虑对于每一个不为 的数 ，若其之前没有访问过，则将所有 全部标记，并将所有底数为 的数全部列出。可以将底数全部改为 然后同样的修改指数的值。问题变为计算有多少本质不同的二元数对 同时满足下列条件：
- （ 是最大的正整数满足 ）
这里定义两个二元数对 和 本质不同当且仅当 。即计数有多少个不同的整数 。因为 的上界一直都是定值 ，而 的上界为 级别约等于 ，所以这个直接随便暴力预处理一下即可。
int buc[32];
unsigned char mp[20000100], vis[2000100];
void run() {
int n = read(), m = read();
int s = 1, tot = 0;
for (int i = 1; i <= 20; ++i) {
for (int j = 1; j <= m; ++j) {
if (!mp[i * j]) ++tot;
mp[i * j] = 1;
}
buc[i] = tot;
}
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
int j = i, pw = 0;
while (j <= n) {
++pw;
vis[j] = 1;
j *= i;
}
s += buc[pw];
}
}
cout << s << '\n';
}
喜欢的话，留下你的评论吧～