题解：P14304 【MX-J27-T1】分块

flying_bluecat · 2025-10-25 13:16:09 · 题解

题解：P14304 【MX-J27-T1】分块

闲话少说

本题数学题，还是比较简单的，放在 CSP-J 里大概 T1-2 的水平。

题意

题目让我们找到对于每一个不超过 n 的数 x 满足 x 是 \lfloor \sqrt{x} \rfloor 的因数的数量。说人话就是有多少个小于等于 n 的数是自身开根号取整后的数的因数。

那根据题面，很容易想到可以通过枚举小于 \sqrt{n} 的整数，我们称其为 c，对于每个 c 我们验证其乘方后的范围内有多少个数是满足条件的即可求出答案。时间复杂度 O(q\times n)。

# include <bits/stdc++.h>
using namespace std;
int q;
long long check(long long x, long long n) {
    long long l = x*x, r = min((x+1)*(x+1)-1, n), ans = 0;
    for (long long i = l; i <= r; ++i) {
        if (!(i % x)) {
            ans++;
        }
    }
    return ans;
}
int main() {
    cin >> q;
    while (q--) {
        long long n, cnt=0;
        cin >> n;
        for (long long i = 1; i <= sqrt(n); ++i) {
            long long ans = check(i, n);
            cnt+=ans;
        }
        cout << cnt << endl;
    }

    return 0;
}

优化思路及数学证明

考虑数学思路优化。

以 10 来举例。我们注意到，满足 n=10 的所有 x 如下：

不难证明，在所有 n 都是平方数的情况下，满足题意的 x 的数量为 \lfloor \sqrt{n} \rfloor \times 3。如果 n 不是平方数，只需要最后删去超出 n 的情况微调即可。时间复杂度 O(q)。

最后别忘了开 long long。

代码如下：

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

int main() {
    cin >> q;
    while (q--) {
        long long n, cnt=0;
        cin >> n;
        long long sq = (long long)(sqrt(n));
        cnt += (sq*3);
        for (long long i = sq+2; i >= sq; --i) {
            if (i*sq > n) {
                cnt--;
            }
        }
        cout << cnt << endl;
    }

    return 0;
}