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

· · 题解

核心思想：找规律。

Part 1 暴力做法

直接按照题意模拟，可以获得 30 分（提交记录）。

这一部分非常简单，观察题目发现要找满足 1\le x\le n 并且 \lfloor\sqrt{x}\rfloor 为 x 的因数的整数 x 的数量。直接看代码（如下）。

#include<bits/stdc++.h>
#define int long long
#define INF 1145141919810
using namespace std;
int q,n;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>q;//多测
    while(q--){
        cin>>n;
        int ans=0;//统计
        for(int i=1;i<=n;i++)
            if(i%((int)sqrt(i))==0)
                ans++;//符合条件
        cout<<ans<<"\n";
    }
    return 0;
}

Part 2 正解观察

看着这道题就感觉有规律可循，所以我们直接弄一组 q=50,n_i=i 的数据。

跑出来：

1
2
3
4
4
5
5
6
7
7
7
8
8
8
9
10
10
10
10
11
11
11
11
12
13
13
13
13
13
14
14
14
14
14
15
16
16
16
16
16
16
17
17
17
17
17
17
18
19
19

稍加观察，就可以发现一定规律并对其进行分组：

1 2 3
4 4 5 5 6
7 7 7 8 8 8 9
10 10 10 10 11 11 11 11 12
13 13 13 13 13 14 14 14 14 14 15
16 16 16 16 16 16 17 17 17 17 17 17 18
19 19 ...
...

发现对于第 i 行（第 i 组），共有 2\times i+1 个数字，其中前面 i 个为 3\times i-2，中间 i 个为 3\times i-1，最后一个为 3\times i。然后就可以差不多写出正解了。

Part 3 半个正解

按照上文去枚举 i，即可获得 50 分（提交记录）。这里来详细讲一下，假设我们已经知道了 n 位于第 i 行，我们如何推出答案。

我们需要确定 n 在第 i 行中的位置。显然，我们需要去除 n 在前面 i-1 行中的部分；运用高斯求和（对于前面 i 行包含的数字数量，可以表示为 \frac{1}{2}\times(3+2\times i+1)\times i=i\times(i+2)）可知前面 i-1 行共有 (i+1)(i-1) 个数字，所以需要让 n 变为 n-(i+1)(i-1) 之后进行取模。然后按照上文去判断即可，注意如果是最后一个那么取模后的结果是 0（可以发现，其实是不需要取模的，不过我就按照赛时取模的想法写出来了）。

如果 n 位于第 i，那么显然 n 有一个限定范围的区间。上面已经求出前面 i-1 行共有 (i+1)(i-1) 个数字，前 i 行共有 i\times(i+2) 个数字，所以 i 要满足 (i+1)(i-1)<n\le i\times(i+2)。这样就能找到 i 了。

代码如下。

#include<bits/stdc++.h>
#define int long long
#define INF 1145141919810
using namespace std;
int q,n;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>q;
    while(q--){
        cin>>n;
        int ans=0,kkl=0;
        for(int i=0;;i++){
            int x=i;
            if((x+1)*(x-1)<n&&n<=(x+2)*x){
                ans=x;//找出 i，用 ans 表示
                break;
            }
        }
        int modu=(n-(ans+1)*(ans-1))%(ans*2+1);//位置
        if(modu==0)kkl=3;
        else if(modu<=ans)kkl=1;
        else kkl=2;//判断
        cout<<(ans-1)*3+kkl<<"\n";//输出
    }
    return 0;
}

Part 4 正解

我们发现 Part 3 时间复杂度太高，达到了 O(\sqrt{n})（因为 i\times(i+2) 大概在 i^2 级别），而我们发现，i 大概就在 \sqrt{n} 附近。所以可以优化。

一个无脑做法：直接从 \sqrt{n} 开始往两边扫。

……