【BZOJ 1853】[Scoi2010] 幸运数字

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1853

这个题，乍一看，跟2393一样。
再一看，确实是一样的QAQ

就只有一个小问题：会不会爆long long
一开始我想，哼，怎么可能爆long long？ 不是要中途除掉一个gcd吗？(￢︿￢)
于是我就在hzwer的程序上加了一个判断：如果爆了long long输出“fuck！！！”
然后效果大概是这样的：
↓↓↓↓↓↓这个是GIF，要点开才能感受到来自心灵的震撼！↓↓↓↓↓↓

大神我错了！！！/(ㄒoㄒ)/~~

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 20000;

int cnt,tot;
LL arr[MAXN],buf[MAXN],l,r,vout;

void DFS(LL w){
	if (w > r) return;
	buf[++cnt] = w;
	DFS(w*10+6);
	DFS(w*10+8);
}

inline void prework(){
	DFS(6); DFS(8);
	sort(buf+1,buf+cnt);
	for (int i=1,tag=0;i<=cnt;i++,tag=0) {
		for (int j=i-1;j;j--) if (buf[i]%buf[j]==0) {tag=1;break;}
		if (!tag) arr[++tot] = buf[i];
	} 
	for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

LL GCD(LL a, LL b){return b?GCD(b,a%b):a;}

void solve(int step, int sz, LL w){
	if (step == tot+1) {
		if (sz & 1) vout += r/w - (l-1)/w;
		else if (sz) vout -= r/w - (l-1)/w;
	} else {
		solve(step+1,sz,w);
		double tmp = (double)w*arr[step]/GCD(w,arr[step]);
		if (tmp <= r) solve(step+1,sz+1,w/GCD(w,arr[step])*arr[step]); 
	}
}

int main(){
	scanf("%lld%lld",&l,&r);
	prework();
	solve(1,0,1);
	printf("%lld\n",vout);
	return 0;
}