专栏文章

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

WWangyixi007
P14304题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mini9hn2
此快照首次捕获于
2025/12/02 02:51
3 个月前
此快照最后确认于
2025/12/02 02:51
3 个月前
查看原文
Update on 2025/10/28 修改了代码中的 sqrt 为 sqrtl，能够通过 hack 数据

0x00 暴力

考虑从 11 开始枚举至 nn，依次判断若不计开根号的复杂度，则显然时间复杂度为 O(nq)O(nq)。
期望得分：30\red{30}。

0x01 正解

首先注意到假设有一个非零自然数 xx，则显然有：
⌊x2⌋=⌊x2+1⌋=…=⌊(x+1)2−1⌋=x\lfloor\sqrt{x^2}\rfloor=\lfloor\sqrt{x^2+1}\rfloor=\ldots=\lfloor\sqrt{{(x+1)}^2-1}\rfloor=x
所以我们考虑在区间 [x2,(x+1)2−1][x^2,{(x+1)}^2-1] 中寻找符合条件的。
因为在区间 [x2,(x+1)2−1][x^2,{(x+1)}^2-1] 中，他们的算术平方根向下取整都为 xx，所以符合条件的个数为：
(x+1)2−1−x2+xx=x2+2x+1−1−x2+xx=3xx=3\frac{(x+1)^2-1-x^2+x}{x}=\frac{x^2+2x+1-1-x^2+x}{x}=\frac{3x}{x}=3
所以在区间 [x2,(x+1)2−1][x^2,{(x+1)}^2-1] 中一定会有 33 个符合条件的数。
然后再考虑一般情况：
首先，我们一定能求出一个 sum=⌊n⌋sum=\lfloor\sqrt{n}\rfloor，则在包含 nn 的区间前，一共会有 3(sum−1)3(sum-1) 个符合条件的数，然后可以处理区间 [sum2,n][{sum}^2,n] 中的符合条件的数的个数：
n−sum2+sumsum\frac{n-{sum}^2+sum}{sum}
所以甚至可以总结公式：
3(⌊n⌋−1)+n−⌊n⌋2+⌊n⌋⌊n⌋3(\lfloor\sqrt{n}\rfloor-1)+\frac{n-{\lfloor\sqrt{n}\rfloor}^2+\lfloor\sqrt{n}\rfloor}{\lfloor\sqrt{n}\rfloor} CPP
#include<bits/stdc++.h>

#define int long long

using namespace std;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t,n;
	int sum,ans,num;
	cin>>t;
	while(t--){
		cin>>n;
		sum=floor(sqrtl(n));
		ans=(sum-1)*3;
		num=sum*sum;
		ans+=(n-num+sum)/sum;
		cout<<ans<<'\n';
	}
    return 0;
}
时间复杂度：O(q)O(q)（不计算开平方的时间）。
预期得分：100\green{100}。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...