【BZOJ 1853】【SCOI 2010】幸运数字

本文主要是介绍【BZOJ 1853】【SCOI 2010】幸运数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直接容斥即可，是的这个做法不会爆，不会爆，不会爆。。。
可以发现，在容斥不断找lcm的时候，这些数字之间的gcd很小，只需少量的几个数字就可以直接爆掉区间上限，很快就能结束（也就是说位数较多的那几个数根本不可能参与容斥），反正最后做出来是对的就行了。。。
有一个问题：输入上限是1e10，如果两个数很大，求lcm可能会导致爆long long。。。。这个时候就要用先把结果暂存在一个double变量里面，比较一下是不是超过区间上限，如果没有超过再继续容斥下去。

#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 10000
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
ll l,r,res;
int tot,n,i,j;
ll a[N],b[N];
int vis[N];
void prod(int x,ll y)
{if (y > r) return; if (x) a[++tot] = y;prod(1,y*10+6); prod(1,y*10+8);
}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
void dfs(int x,int y,ll z)
{if (x > n){if (y&1) res += r / z - (l-1) / z;else if (y) res -= r / z - (l-1) / z;return;}dfs(x+1,y,z);ll tmp = z / gcd(a[x],z);if (((double)a[x]*tmp)<=r)dfs(x+1,y+1,a[x]*tmp);
}
int main()
{scanf("%lld%lld",&l,&r);prod(0,0);sort(a+1,a+tot+1);fo(i,1,tot)if (!vis[i]){b[++n] = a[i];fo(j,i+1,tot)if (a[j] % a[i] == 0) vis[j] = 1;}fo(i,1,n) a[n-i+1] = b[i];dfs(1,0,1);printf("%lld",res);
}