自动搬运

查看原文

来自洛谷，原作者为

	Alarm5854 Stop Smoking!

搬运于2025-08-24 22:31:17，当前版本为作者最后更新于2021-05-06 14:40:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题目一看数据范围就知道它是一道数学题，不过要怎样处理呢？

令 $f(x)$ 为不能整除 $x$ 的最小整数，其中 $x\ge 3$，很显然的是 $\text{strength}(x)=\text{strength}(f(x))+1$，这根据定义可知。

关键就在这里：对于所有 $x\in [3,10^{17}]$，一定有 $f(x)\le 41$，因为 $\text{lcm}(1,2,...,40)<10^{17}$，而 $\text{lcm}(1,2,...,41)>10^{17}$，所以只需要预处理一下 $3$ 到 $41$ 之间的 $\text{strength}(i)$ 即可。

预处理完之后，计算 $3$ 到 $n$ 的 $\text{strength}(i)$ 的和。答案初始化为 $2n+k$，其中 $k$ 为任意常数，因为之后计算答案的时候可以抵消，枚举 $2$ 到 $40$，并更新 $\text{lcm}$，再更新答案即可。

#include<ctime>
#include<cstdio>
#include<cctype>
#define ll long long
using namespace std;
ll read(){
	char c;
	ll x=0,f=1;
	while(!isdigit(c=getchar()))
		f-=2*(c=='-');
	while(isdigit(c)){
		x=x*10+f*(c-48);
		c=getchar();
	}
	return x;
}
ll gcd(ll x,ll y){
	while(x&&y){
		ll z=x;
		x=y;
		y=z%y;
	}
	return x|y;
}
ll lcm(ll x,ll y){
	return x/gcd(x,y)*y;
}
ll a,b,str[55];
ll f(ll x){//找最小的正整数使得不能整除x
	ll t=2;
	for(;;++t){
		if(x%t)
			break;
	}
	return t;
}
ll work(ll x){
	ll tmp=1;
	ll res=x*2;
	for(ll i=2;i<43;++i){
		tmp=lcm(tmp,i);
		res+=x/tmp*(str[i+1]-str[i]);//在1~x中f(i)>tmp的有x/tmp个，而这些开始默认它为tmp，所以要改变
	}
	return res;
}
int main(){
	a=read()-1;
	b=read();
	for(ll i=3;i<=43;++i)
		str[i]=str[f(i)]+1;//预处理strength(i)，实际上并不需要确切值，像这里其实处理的是strength(i)-1
	printf("%lld",work(b)-work(a));
	return 0;
}