SP22382 题解

Galex · 2022-06-20 10:06:05 · 题解

首先发现 T 很大，现场去求肯定超时，所以考虑预处理。

先对 1 \sim 10^6 的每个数求出它们的欧拉函数值，这个把质数筛出来就行。

设 f[i][j] 为 i 是否刚好经过 j 次变换后变为 1，特别的，f[1][0]=1，因为 1 不经过欧拉函数的变换就是 1。

然后对于所有 i \in [2,10^6],j \in [1,20] 求出 f[i][j]，显然有递推公式 f[i][j]=f[\varphi(i)][j-1]。

最后用前缀和处理一下，即可做到 O(1) 查询。记 ans[i][j] 表示 1 \sim i 有多少个数经过 j 次变换后恰好为 1，有递推公式 ans[i][j]=ans[i-1][j]+f[i][j]。

那么每次查询的答案即为 ans[n][k]-ans[m-1][k]。

代码：

#include <bits/stdc++.h>
using namespace std;

int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9')
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

bool p[1000005];
int pr[1000000], tot = 0;
int ls[1000005], phi[1000005], ans[1000005][25] = {{0}};
bool f[1000005][25] = {{0}};

void szs(int n) {
    memset(p, true, sizeof p);
    p[0] = p[1] = false;
    for (int i = 2; i <= n; i++) {
        if (p[i])
            pr[++tot] = i, ls[i] = i;
        for (int j = 1; j <= tot && i * pr[j] <= n; j++) {
            p[i * pr[j]] = false, ls[i * pr[j]] = pr[j];
            if (i % pr[j] == 0)
                break;
        }
    }
}

int Phi(int x) {
    int z[15], tot = 0, ans = x;
    while (x != 1) {
        int k = ls[x];
        if (z[tot] != k)
            z[++tot] = k;
        x /= k;
    }
    for (int i = 1; i <= tot; i++)
        ans = ans / z[i] * (z[i] - 1);
    return ans;
}

int main() {
    szs(1000000);
    for (int i = 1; i <= 1000000; i++)
        phi[i] = Phi(i);
    ans[1][0] = 1, f[1][0] = true;
    for (int i = 2; i <= 1000000; i++)
        for (int j = 0; j <= 20; j++)
            ans[i][j] = ans[i - 1][j] + (f[i][j] = f[phi[i]][j - 1]);
    int T = read();
    while (T--) {
        int l = read(), r = read(), k = read();
        printf("%lld\n", ans[r][k] - ans[l - 1][k]);
    }
    return 0;
}