＜P2567 [SCOI2010] 幸运数字＞

题目背景

四川 NOI 省选 2010。

题目描述

在中国，很多人都把 6 和 8 视为是幸运数字！lxhgww 也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字 6 和 8 的那些号码，比如 68，666，888 都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在 [1,100] 的区间内就只有 6 个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww 规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如 12，16，666 都是“近似幸运号码”。

现在 lxhgww 想知道在一段闭区间 [a,b] 内，“近似幸运号码”的个数。

输入格式

输入数据是一行，包括 2 个数字 a 和 b。

输出格式

输出数据是一行，包括 1 个数字，表示在闭区间 [a,b] 内“近似幸运号码”的个数。

输入输出样例

输入 #1复制

1 10

输出 #1复制

2

说明/提示

对于 30% 的数据，保证 1≤a≤b≤106。

对于 100% 的数据，保证 1≤a≤b≤1010。

代码实现:

#include <iostream> #include <algorithm> #include <cmath> #define int long long using namespace std; const int N=1e6+9; int x, y, res; int lst[N], t, lc[N], len; bool mk[N]; void dfs(int s) { if(s > y) return; if(s) lst[++t] = s; dfs(s*10+6); dfs(s*10+8); } bool cmp(int a, int b) { return a>b; } __int128 gcd(__int128 a, __int128 b) { if(!b) return a; else return gcd(b, a%b); } __int128 lcm(__int128 a, __int128 b) { if(!a) return b; return a/gcd(a,b)*b; } void dfs2(int idx, int cnt, __int128 lm) { if(lm > y) return; if(idx > len) { if(!lm) return; int sign = (cnt%2) ? 1 : -1; res += sign * (floor(1.0*y/lm) - ceil(1.0*x/lm) + 1); return; } dfs2(idx+1, cnt+1, lcm(lm, lc[idx])); dfs2(idx+1, cnt, lm); } signed main() { scanf("%lld%lld", &x, &y); dfs(0); for(int i=1; i<=t; ++i) { if(!mk[i]) lc[++len] = lst[i]; for(int j=i+1; j<=t; ++j) if(!(lst[j] % lst[i])) mk[j] = true; } sort(lc+1, lc+1+len, cmp); dfs2(1, 0, 0); printf("%lld", res); return 0; }