自动搬运

查看原文

来自洛谷，原作者为

	yybyyb **

搬运于2025-08-24 21:39:09，当前版本为作者最后更新于2018-08-03 19:50:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

成功轰下你谷rk1，甚至超越了一个打表选手
这题思路很明显吧，先搞出来所有范围内的合法数字，然后直接容斥，
容斥的话显然没有别的办法解决，只能够爆搜，
那么我们就来大力剪枝：
1.如果当前的所有选定的数的$lcm$大于$r$直接退出，这不显然吗。。
2.如果一个合法数字是另外一个合法数字的倍数，那么这个数没有意义，这不还是显然吗。
3.把合法的所有数字从大往小排序，这样爆搜的时候更快突破边界。
好了，这样子就可以在洛谷上$AC$了，然而$BZOJ$总时限并过不去。
接着剪枝，现在因为所有数都不满足是另外一个数的倍数，
所以合并任意两个数的时候，$lcm$的最小情况就是乘上一个$3$。
所以对于所有$>r/3$的合法数字，显然不能够和任何一个数合并了，
所以这一部分可以拿出来直接提前算好，再用剩下的数字爆搜就好啦。
也许底下那个题解说只提前考虑r/2的值就是没我快的原因吧。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
int tot;
ll a[5050],ret,l,r;
void dfs(ll x){if(x>r)return;if(x)a[++tot]=x;dfs(x*10+6);dfs(x*10+8);}
const int MOD=1000000007;
bool check(ll a,ll b)
{
	int A=a/MOD,B=b/MOD;
	if(A*B)return true;
	return a*b>r;
}
void calc(int x,ll s,int cnt)
{
    if(x>tot&&s!=1)
    {
        if(cnt&1)ret+=r/s-l/s;
        else ret-=r/s-l/s;
        return;
    }
    if(x>tot)return;
    calc(x+1,s,cnt);
	ll d=a[x]/__gcd(s,a[x]);
    if(!check(s,d))calc(x+1,s*d,cnt+1);
}
bool vis[5050];
ll Work()
{
	dfs(0);sort(&a[1],&a[tot+1]);
	int t=0;
	for(int i=1;i<=tot;++i)
		for(int j=1;j<i;++j)
			if(a[i]%a[j]==0){vis[i]=true;break;}
	for(int i=1;i<=tot;++i)
		if(!vis[i])
		{
			if(a[i]<=r/3)a[++t]=a[i];
			else ret+=r/a[i]-l/a[i];
		}
	tot=t;reverse(&a[1],&a[tot+1]);calc(1,1,0);
	return ret;
}
int main()
{
	cin>>l>>r;--l;
	cout<<Work()<<endl;
	return 0;
}