自动搬运

查看原文

来自洛谷，原作者为

	zhuweiqi 攀峰之高险，岂有崖颠；搏海之明辉，何来彼岸？前进不止，奋斗不息。

搬运于2025-08-24 22:50:06，当前版本为作者最后更新于2023-09-08 20:49:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一眼数论题。

观察到数据范围是 $m\leq 10^{12}$，因此我们需要使用 $O(\sqrt{m})$ 及以下时间复杂度的做法才能通过，首先考虑 $O(m)$ 的筛倍数法，即枚举每个因数 $i$，找到最小的 $L$ 和 $R$ 使得 $n\leq i\times L$ 并且 $i\times R\leq m$，这意味着范围内一共有 $R-L+1$ 个数有 $i$ 这个因数，然后考虑优化，我们在枚举因数 $i$ 的时候可以顺便把 $L$ 至 $R$ 范围内的所有正整数也当成因数把贡献值加上，这样一来，由于约数总是成对出现的，我们只需要枚举所有不大于 $\sqrt{m}$ 的因数，那些大于 $\sqrt{m}$ 的因数就自然而然地也会被筛一遍了，我们的时间复杂度就可以降为 $O(\sqrt{m})$ 了，考虑到当 $x$ 是完全平方数时因数 $\sqrt{x}$ 会被重复计算两次，故我们需要将贡献值减去范围内的完全平方数的个数。参考代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll l,r,L,R,ans=0;
	scanf("%lld%lld",&l,&r);
	for(ll i=1;i*i<=r;i++) if(i*i>=l) ans--;
	for(ll i=1;i*i<=r;i++){
		l=max(l,i*i);
		L=(l+i-1)/i;
		R=r/i;
		if(L<=R) ans+=(R-L+1)<<1;
	}
	printf("%lld",ans);
    return 0;
}