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

简单题。场切了。

考虑

\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

中，只要特判就行了。

代码：

CPP

#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;
}

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

文章操作

相关推荐

评论

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