【MX-J27-T1】分块

_H17_ · 2025-10-25 12:52:08 · 题解

题目分析

对于答案 y，y^2,y(y+1),y(y+2) 是可行的。因为 y(y+2)<(y+1)^2。

我们发现 (\lfloor\sqrt{x}\rfloor-1)^2+1\le x，然后枚举 \lfloor\sqrt{x}\rfloor,\lfloor\sqrt{x}\rfloor+1 即可。

时间复杂度 O(q)。

代码

#include<bits/stdc++.h>
#define int long long
#define ALL(x) x.begin(),x.end()
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
using namespace std;
constexpr int N=1e5+1,Inf=0x3f3f3f3f3f3f3f3fll;
void read(int&x){
    x=0;
    int f=1;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x*=f;
    return;
}
void write(int val){
    if(val>=10)
        write(val/10);
    putchar((val%10)^48);
    return;
}
void writeln(int x){
    write(x);
    putchar('\n');
    return;
}
int q,n,x,ans;
signed main(){
    for(read(q);q;--q){
        read(n);
        x=sqrt(n);
        ans=3*(x-1);
        if(x*x<=n)
            ans++;
        if(x*(x+1)<=n)
            ans++;
        if(x*(x+2)<=n)
            ans++;
        if((x+1)*(x+1)<=n)
            ans++;
        if((x+1)*(x+2)<=n)
            ans++;
        if((x+1)*(x+3)<=n)
            ans++;
        cout<<ans<<'\n';
    }
    return 0;
}