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

zhujianheng · 2025-10-25 12:10:27 · 题解

简单题。场切了。

考虑 \sqrt n 下取整什么时候能被 n 整除。

记 \sqrt n 下取整为 k，则 k^2 \le n < (k+1)^2，所以 k^2 \le n < k^2+2k+1，k^2 \le n \le k^2+2k，又 k|n，所以 \dfrac{n}{k} 只有三个值 k，k+1，k+2（因为 k 是正整数，所以当 a>2 时 k^2+ak>k^2+2k，a<0 时，k^2+ak<k^2）。

所以在 1 到 k^2-1 中，有 3(k-1) 个这样的正整数。k^2 到 n 中，只要特判就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Q=100009;
int x[Q],q;
signed main(){
    ios::sync_with_stdio(0);
    cin>>q;
    for(int i=1;i<=q;i++) cin>>x[i];
    for(int i=1;i<=q;i++){
        int k=sqrt(x[i]);
        int ans=0;
        if(k==1){cout<<x[i]<<endl;continue;}
        ans+=3*(k-1);
        if(x[i]>=k*k) ans++;
        if(x[i]>=k*(k+1)) ans++;
        if(x[i]>=k*(k+2)) ans++;
        cout<<ans<<'\n';
    }
    return 0;
}