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

ningyy · 2025-10-25 12:42:41 · 题解

题意

给定一个数 n，求 1\sim n 中有多少数满足 \lfloor\sqrt x\rfloor 是 x 的因数。

思路

容易注意到，对于一个数 x，在 x^2\sim{(x+1)^2-1} 中只有 3 个数符合条件，分别是 x^2,x^2+x,x^2+2x，证明显然，那么直接计算 \sqrt n-1 的总个数，再判断对于 \sqrt n 的三个数是否在范围内即可。

代码

注意开 long long，以及用 sqrtl，避免掉精度。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(;n--;){
        cin>>x;
        int m=sqrtl(x);
        int ans=(m-1)*3;
        if(m*m<=x) ans++;
        if(m*(m+1)<=x) ans++;
        if(m*(m+2)<=x) ans++;
        cout<<ans<<"\n";
    }
    return 0;
}