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

fallstars · 2025-10-25 13:13:37 · 题解

计算得到对于所有整数 i ，i^2 + xi 在 i^2 + xi < (i + 1)^2 时都满足条件，且其他情况不满足。

展开平方式 (i + 1)^2 得到 i^2 + 2i + 1 ，则 i^2 + 2i = (i + 1)^2 - 1 ，原来的式子变成 i^2 + xi \le i^2 + 2i , x \le 2 。所以对于每一个 i 都有三个数满足条件。而按题意得 i^2 \le n , i \le \sqrt n ， 那么只需要对于 \lfloor \sqrt n \rfloor 分类讨论即可。

最后注意不要用标准的 sqrt 函数，会爆 long long ，要用二分查找平方根。时间复杂度 O(\log n) 。

AC CODE

#include<iostream>
using namespace std;
long long q,n;
long long sqrts(long long n)
{
    long long l = 1,r = 1e9;
    while(l <= r)
    {
        long long mid = (l + r) >> 1;
        if(mid * mid > n) r = mid - 1;
        else l = mid + 1;
    }
    return r;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> q;
    while(q--)
    {
        cin >> n;
        long long sqrtnum = sqrts(n);
        if(sqrtnum * sqrtnum + sqrtnum > n) cout << 3ll * (sqrtnum - 1) + 1;
        else if(sqrtnum * sqrtnum + sqrtnum <= n && sqrtnum * sqrtnum + sqrtnum * 2 > n) cout << 3ll * (sqrtnum - 1) + 2;
        else cout << 3ll * sqrtnum;
        cout << '\n';
    }
}