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

YC_15873137308 · 2025-10-25 13:02:07 · 题解

P14303分块题目传送门

题目大意

有 q 次询问，每次询问有一个数 n ，在 1 ~ n 中,对于每一个数 x ,统计 ⌊\sqrt x⌋ 是 x 的因数个数

题目分析

这是一道模拟题（或是一道纯数学题）

对于每一个 ⌊\sqrt x⌋ ,我们可以发现：

若保证 ⌊\sqrt x⌋ 是 x 的因数，在区间 x^2 到 (x+1)^2 - 1 中，只有 3 个数满足条件，具体推论如下：

因为完全平方数之间的差值是一个差值为 2 的等差数列。对于区间 x^2 到 (x+1)^2 中，之间的数有

所以满足条件的数为：

所以在区间 x^2 到 (x+1)^2 - 1 中，只有 3 个数满足条件

由于 n 不保证是一个完全平方数，我们将其拆成前 (⌊\sqrt x⌋ - 1)^2 和 ⌊\sqrt x⌋^2 到 n 之间

前 (⌊\sqrt x⌋ - 1)^2 就不说了，是 （⌊\sqrt x⌋ - 1）\times 3 ，已经推过了

在后 ⌊\sqrt x⌋^2 到 n 之间

我们把 n 变为 n - (n \mod ⌊\sqrt x⌋)

因为在 n 附近满足条件的数只有 n - (n \mod ⌊\sqrt x⌋) 和 n - (n \mod ⌊\sqrt x⌋) + ⌊\sqrt x⌋

所以在 n - (n \mod ⌊\sqrt x⌋)+1 到 n 之间没有满足条件的数（保证 n \ne n - (n \mod ⌊\sqrt x⌋ ) ）

当 n = n - (n \mod ⌊\sqrt x⌋ ) 时，则不变

所以在 ⌊\sqrt x⌋^2 到 n 之间

满足条件的数就是 (n - (n \mod ⌊\sqrt x⌋) - s^2 ) \div s + 1

那代码就很简单了

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int main(){
//  freopen("sqrt.in","r",stdin);
//  freopen("sqrt.out","w",stdout);
    scanf("%d",&n);
    while(n--){
        ll k;
        scanf("%lld",&k);
        ll ans = 0;
        ll s = sqrt(k);
        --s;
        ans += s * 3;
        ++s;
        ans += (k - (k % s) - s*s) / s + 1;
        printf("%lld\n",ans);
    }
    return 0;
}