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

qwqSW · 2025-10-25 12:48:28 · 题解

题目传送门

My Blog

我们发现这个题是 T1，但它的 n 很大，于是我们可以合理推断这是个结论题或诈骗题。

我们考虑 [m^2,(m+1)^2) 这个区间里有哪些数满足题中所述的条件。显然 [1^2,2^2),[2^2,3^2), \cdots ,[m^2,(m+1)^2),[(m+1)^2,(m+2)^2), \cdots 这些区间拼起来肯定是连续的，不会少算答案。

这样的好处很显然，可以直接去掉根号下取整，也就是对于这个区间里的任意一个数 x，\lfloor \sqrt{x} \rfloor = m。

这样的话问题就转换成了这个区间里有多少 m 的因数。那不就是 m^2,m^2+m,m^2+2m 这三个嘛（因为 (m+1)^2=m^2+2m+1，所以 m^2+3m,m^2+4m 及之后的数并不在这个区间内）。

也就是对于所有形如这样的区间，都只有 3 个数满足条件。

所以我们对于每个 n，找到最大的一个正整数 m 使得 m^2 \le n，这样最后一个在区间范围内的、形如上述区间的区间就是 [(m-1)^2,m^2)，所以前面会有 m-1 个这样的区间，答案就会先累加一个 3(m-1)。

接下来对 n 分类讨论一下，看看对于 [m^2,(m+1)^2) 这个区间，m^2,m^2+m,m^2+2m 这三个数是否小于 n 即可，小于则将它们累加进答案。

代码：

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

inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<48){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}

int q;

inline int erfen(int x){
    int l=1,r=x;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(mid*mid<=x){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }
    return l;
}

signed main(){
    q=read();
    while(q--){
        int n=read();
        int fang=erfen(n);
        //为了防止sqrt下取整有误差，我用了一个手写二分 
        int ans=3*fang-3;
        //第一次累加答案，然后分讨
        if(n<fang*(fang+1)){//只能取m^2
            ans+=1;
        }
        else if(n<fang*(fang+2)){//能取的是m^2,m^2+m 
            ans+=2;
        }
        else{//m^2,m^2+m,m^2+2m三个数都能取 
            ans+=3;
        }
        write(ans);printf("\n");
    }
    return 0;
}

喜欢的话不妨点点赞呀 qwq