幸运数字(容斥)
枫林晚
2018-03-02 23:20:06
2018年3月2日23:07:36
洛谷P2567
要点:
很容易考虑到容斥。先预处理出所有幸运数字,加上它们的倍数个,再找所有两个的最小公倍数减去倍数个,再加上3的……
至于[a,b],“前缀和”思想处理即可。
但是暴力的考虑复杂度2^2046,tle;
所以要考虑如下剪枝:
1.如果b|a,那么对于所有的x|b,都有x|a,所以这样的b是没有用的。去掉所有的“伪幸运数字”,还有943个。
2.循环时,当这时的LCM已经大于b时,可以直接不要,因为之后若再取LCM,只能更大,都不会满足要求,回溯。
3.将所有的真幸运数字由大到小排序,可以使得LCM更快的超过b。例如:5,4,3,2,1;假如这次要取5,4,3,2,1的最小公倍数,而b是18,若从大到小,那么取了5,4就可以回溯了;反之,要取1,2,3,4才能回溯。
至于代码实现:
1.找幸运数字直接枚举。去伪的时候,标记一下。(n方复杂度)
2.容斥采用dfs(算容斥时很好用),标记一下取数的个数。奇数的LCM加上倍数个,反之减去。
3.“b-(a-1)”可以直接算,不用循环两遍。
(4.疑问:为什么要乘1.0)
解答:
本身kk ** num[dep]有可能会爆long long 所以乘1.0变成float型,(float范围 -3.4* -1e38)~3.4* 1e38)足矣)
(double范围: -1.7* -1e308)~1.7* 1e308)
(long double范围:-1.2* -1e4932~1.2* 1e4932)
或者更好的方法是:移项;
if(kk<=B/num[dep]) 这样一定不会爆long long
代码如下:
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+5;
ll A,B;
ll num[N],a[N];
bool mark[N];
ll ans,tot,sum,n;
void dfs1(int dep,int cnt,ll val)
{
//if(val>b) return;
if(dep>cnt) return;
if(dep==cnt)
{
a[++tot]=val;
return;
}
dfs1(dep+1,cnt,val*10+6);
dfs1(dep+1,cnt,val*10+8);
}
void sieve()
{
for(int i=1;i<=tot;i++)
{
if(!mark[i]) num[++n]=a[i];
for(int j=1;j<=tot;j++)
if(a[j]%a[i]==0) mark[j]=1;
}
}
bool cmp(ll a,ll b)
{
return a>b;
}
ll gcd(ll a,ll b)
{
if(a<b) swap(a,b);
ll g=b;
while(1)
{
ll k=a%b;
if(k==0) break;
g=k;a=b;b=g;
}
return g;
}
ll zhi(ll t)
{
return B/t-(A-1)/t;
}
void dfs2(int dep,int cnt,ll val)
{
if(val>B) return;
if(dep>n)
{
if(cnt==0) return;
ll now=zhi(val);
ans+=now*((cnt&1)?1:-1);
return;
}
dfs2(dep+1,cnt,val);
ll kk=val/gcd(val,num[dep]);
if(1.0*kk*num[dep]<=B)
dfs2(dep+1,cnt+1,kk*num[dep]);
}
int main()
{
scanf("%lld%lld",&A,&B);
for(int i=1;i<=10;i++)
dfs1(0,i,0);
sieve();//sieve:筛;
sort(num+1,num+n+1,cmp);
dfs2(1,0,1);
printf("%lld",ans);
return 0;
}
```