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

· · 题解

Update on 2025/10/28 修改了代码中的 sqrt 为 sqrtl，能够通过 hack 数据

0x00 暴力

考虑从 1 开始枚举至 n，依次判断若不计开根号的复杂度，则显然时间复杂度为 O(nq)。

期望得分：\red{30}。

0x01 正解

首先注意到假设有一个非零自然数 x，则显然有：

\lfloor\sqrt{x^2}\rfloor=\lfloor\sqrt{x^2+1}\rfloor=\ldots=\lfloor\sqrt{{(x+1)}^2-1}\rfloor=x

所以我们考虑在区间 [x^2,{(x+1)}^2-1] 中寻找符合条件的。

因为在区间 [x^2,{(x+1)}^2-1] 中，他们的算术平方根向下取整都为 x，所以符合条件的个数为：

\frac{(x+1)^2-1-x^2+x}{x}=\frac{x^2+2x+1-1-x^2+x}{x}=\frac{3x}{x}=3

所以在区间 [x^2,{(x+1)}^2-1] 中一定会有 3 个符合条件的数。

然后再考虑一般情况：

首先，我们一定能求出一个 sum=\lfloor\sqrt{n}\rfloor，则在包含 n 的区间前，一共会有 3(sum-1) 个符合条件的数，然后可以处理区间 [{sum}^2,n] 中的符合条件的数的个数：

\frac{n-{sum}^2+sum}{sum}

所以甚至可以总结公式：

3(\lfloor\sqrt{n}\rfloor-1)+\frac{n-{\lfloor\sqrt{n}\rfloor}^2+\lfloor\sqrt{n}\rfloor}{\lfloor\sqrt{n}\rfloor} 
#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t,n;
    int sum,ans,num;
    cin>>t;
    while(t--){
        cin>>n;
        sum=floor(sqrtl(n));
        ans=(sum-1)*3;
        num=sum*sum;
        ans+=(n-num+sum)/sum;
        cout<<ans<<'\n';
    }
    return 0;
}

时间复杂度：O(q)（不计算开平方的时间）。

预期得分：\green{100}。