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

UNNN · 2025-10-25 13:57:20 · 题解

题解交迟了所以没申请

题意

给定一个正整数 n，求存在多少个正整数 x \in [1, n]，使得 x \bmod \lfloor \sqrt{x} \rfloor = 0。

思路

如果直接暴力搜索，由于 n \le 10^{18}，O(n) 显然会超时。

因此，我们可以考虑手动打表来找规律。我们列出 n = 25 时所有 [1, n] 的正整数，并判断其是否合法，如下表：

不难发现，对于每一块具有相同的 \lfloor \sqrt{x} \rfloor 值的 x，都仅存在 3 个合法的 x，这三个数分别是 \lfloor \sqrt{x} \rfloor^2，\frac {\lfloor \sqrt{x} \rfloor^2 + \lfloor \sqrt{x + 1} \rfloor^2 - 1}{2} 和 \lfloor \sqrt{x + 1} \rfloor^2 - 1。

::::info[证明过程]

如果 x 是个完全平方数，那么显然有 \lfloor \sqrt{x} \rfloor = \sqrt{x}，又因为 x = \sqrt{x} \cdot \sqrt{x} = \lfloor \sqrt{x} \rfloor \cdot \lfloor \sqrt{x} \rfloor，故 \lfloor \sqrt{x} \rfloor 必定是 x 的一个因数，且 x = \lfloor \sqrt{x} \rfloor^2。
如果 x + 1 是个完全平方数，根据上述结论有 x + 1 = \lfloor \sqrt{x + 1} \rfloor^2，整理可得 x = \lfloor \sqrt{x + 1} \rfloor^2 - 1。又因为 x + 1 是完全平方数，所以 x 不是完全平方数，它们的算术平方根向下取整后显然不一样，而且由于取整，两者会相差 1，所以有 \lfloor \sqrt{x + 1} \rfloor = \lfloor \sqrt{x} \rfloor + 1。代入 x 可以得到以下式子：

\begin{aligned} x &= (\lfloor \sqrt{x} \rfloor + 1)^2 - 1 \\ &= \lfloor \sqrt{x} \rfloor^2 + 2 \lfloor \sqrt{x} \rfloor + 1 - 1 \\ &= \lfloor \sqrt{x} \rfloor^2 + 2 \lfloor \sqrt{x} \rfloor \\ &= \lfloor \sqrt{x} \rfloor(\lfloor \sqrt{x} \rfloor + 2) \end{aligned}

上式中提出了一个因数 \lfloor \sqrt{x} \rfloor，所以 \lfloor \sqrt{x} \rfloor 必定是 x 也就是 \lfloor \sqrt{x + 1} \rfloor^2 - 1 的一个因数。

对于数 \frac {\lfloor \sqrt{x} \rfloor^2 + \lfloor \sqrt{x + 1} \rfloor^2 - 1}{2}，我们先前已经证明 \lfloor \sqrt{x} \rfloor^2 和 \lfloor \sqrt{x + 1} \rfloor^2 - 1 在模 \lfloor \sqrt{x} \rfloor 意义下同余，故显然两者相加后再乘 2 的逆元依旧在模 \lfloor \sqrt{x} \rfloor 意义下同余。 ::::

接下来就是统计答案，通过上述的表格可以得知，n 可以把这若干个 x 分成 \lfloor \sqrt{n} \rfloor 块。我们令 m = \lfloor \sqrt{n} \rfloor，显然前 m - 1 块合法的 x 总共有 3(m - 1) 个。

对于最后一块，设最后一块有 k 个合法的数：
如果 n 在这一块中第一个合法的数 (含) 到第二个合法的数 (不含) 之间，那么 k = 1；
如果在第二个合法的数 (含) 到第三个合法的数 (不含) 之间，那么 k = 2；
如果正好是第三个合法的数，那么 k = 3。

最后答案就是 3(m - 1) + k。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
ll q, n, m, ans;
bool issq(ll x){ // 判断是否为完全平方数
    ld xx = (ld)sqrt((ld)x);
    return xx == (ll)xx;
}
int main()
{
    scanf("%lld", &q);
    while(q--){
        scanf("%lld", &n);
        m = (ll)sqrt((ld)n); // 计算能分成多少块
        ll l = m * m, r = (m + 1LL) * (m + 1LL), mid = (l + r) >> 1LL; // l, mid, r - 1 分别为最后一块中第一个合法的数，第二个合法的数和第三个合法的数
        // 统计
        if(n >= l && n < mid) ans = (m - 1LL) * 3LL + 1LL;
        else if(n >= mid && n < r - 1LL) ans = (m - 1LL) * 3LL + 2LL;
        else if(n == r - 1LL) ans = m * 3LL;
        printf("%lld\n", ans); // 输出
    }
    return 0; // 结束 (｡･ω･｡)
}