传送门
搜索菜题,然而第一次没有注意然后爆longlonglong longlonglong了。
题意:称所有数位由6,86,86,8组成的数为幸运数字,问一个一个区间[l,r][l,r][l,r]中所有幸运数字及其倍数的个数。
思路:
先把所有的幸运数字找出来并筛去那些会算重的,剩下一共不超过100010001000个数。
即如果满足numi∣numjnum_i|num_jnumi∣numj就删去numjnum_jnumj。
然后考虑直接容斥+搜索算出答案。
现在就只用想怎么剪枝了。
- 当前的lcmlcmlcm大于b
- 把所有数从大到小排序。
- 由于每一次取lcmlcmlcm至少乘三,因此只要一个数是≤b/3\le b/3≤b/3的就不用加入最终的numnumnum集合。
然后直接搜就行了。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const ll divv=1e9;
ll a,b,val[2500],lim,tot=0,ans=0,sig=0,coef[2500];
inline void calc(ll mul){
if(mul>b)return;
if(mul)val[++tot]=mul;
calc(mul*10+6),calc(mul*10+8);
}
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t%a;}return a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline bool check(ll x,ll y){
if((x/divv)*(y/divv))return 0;
return x*y<=b;
}
inline void dfs(int pos,int tim,ll mult){
if(mult>b)return;
if(pos==sig+1){
if(mult==1)return;
ans+=(b/mult-a/mult)*(tim&1?1:-1);
return;
}
dfs(pos+1,tim,mult);
ll x=mult/gcd(mult,coef[pos]),y=coef[pos];
if(check(x,y))dfs(pos+1,tim+1,x*y);
}
int main(){
cin>>a>>b,--a;
calc(0),ans=0;
sort(val+1,val+tot+1);
for(ri i=1;i<=tot;++i){
bool f=1;
for(ri j=1;j<i;++j)if(val[i]==val[i]/val[j]*val[j]){f=0;break;}
if(f){
if(val[i]<=b/3)coef[++sig]=val[i];
else ans+=b/val[i]-a/val[i];
}
}
reverse(coef+1,coef+sig+1);
dfs(1,0,1);
cout<<ans;
return 0;
}