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

Death_Cai · 2025-10-25 12:13:10 · 题解

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

题目大意

给定 q 次询问，每次给出一个正整数 n，需要统计有多少个不超过 n 的正整数 x 满足 \lfloor \sqrt{x} \rfloor 是 x 的因数。

思路

设 k = \lfloor \sqrt{x} \rfloor，那么 x 必须满足 k \mid x 且 k^2 \leq x < (k+1)^2。

对于每个固定的 k，满足条件的 x 是区间 [k^2, (k+1)^2) 中所有能被 k 整除的数。

对于给定的 k，在区间 [k^2, (k+1)^2) 中：

• 第一个满足条件的数是 k^2（因为 k \mid k^2）
• 下一个满足条件的数是 k^2 + k
• 再下一个是 k^2 + 2k，依此类推

区间 [k^2, (k+1)^2) 的长度为 (k+1)^2 - k^2 = 2k + 1。

因此，对于每个 k，满足条件的 x 的数量为：

• 如果 k^2 + 2k < (k+1)^2，则有 3 个满足条件的数：k^2，k^2 + k，k^2 + 2k
• 如果 k^2 + 2k \geq (k+1)^2，则需要特殊处理

实际上，由于 (k+1)^2 - k^2 = 2k + 1，而 2k + 1 通常大于 2k，所以对于 k \geq 1，最多有 3 个满足条件的数。

因此总答案为：

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define str stringstream
#define PII pair<int,int>
const int N=1e5+5;
int t,n;
int solve(int n){
    if(n==0)return 0;
    int k=(int)sqrtl(n);// 计算 sqrtl(n) 的整数部分(一定要用 sqrtl() 不然会炸 90pts)
    if(k==0)return 0;
    // 公式：3*(k-1) + min((n-k^2)/k, 2) + 1
    return 3*(k-1)+min((n-k*k)/k,2ll)+1;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // freopen("sqrt5.in","r",stdin);
    // freopen("sqrt5.out","w",stdout);
    cin>>t;
    while(t--){
        cin>>n;
        cout<<solve(n)<<"\n";
    }
    return 0;
}

感谢阅读。