P2567 [SCOI2010]幸运数字 [容斥+有技巧的搜索]

$幸运数字$

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

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

$最初想法$
预处理出所有的 幸运数字, 存到 $A []$ 数组里, 共有 $c n t$ 个.

设 $[1, x]$ 含有 $F [i]$ 个第 $i$ 个幸运数字的倍数,
枚举 $A_{i}$ 的倍数, 若存在 $A_{i} ∣ A_{j}$ , 则 $F [i] - = F [j]$ .
最后 $A n s = \sum_{i = 1}^{c n t} F [i]$ .

但是这个算法连样例都过不去.

上方算法好蠢 …

错因: 存在 $L c m (A_{i}, A_{j}) ∣ A_{i}$ , 但是由于 $L c m (A_{i}, A_{j})$ 并不一定在 $A []$ 中, 于是 $F [i]$ 没有减去 $L c m (A_{i}, A_{j})$ 对应的 $F$ 值 .

$正解部分$
老实地容斥, 大力地剪枝 .

$优化 1 : 按从大到小排序, 使得 D F S 尽早 b r e a k .$
$优化 2 : 对于 A_{i} ∣ A_{j}, 去掉 A_{j} 无影响$ .
$<mstyle mathcolor="red"> 优化 3 : 对于 A_{i} > b / 3, 其无法与其它数字结合, 直接计入答案 </mstyle>$

$剪枝 1 : 若当前的 L c m 大于右端点, <mtext> </mtext> r e t u r n$

注意 $D F S$ 出来的 $A []$ 数组并不是有序的, 这是因为 $D F S$ 的回溯过程使得数据梯度出现向下的陡坡.

求解 $L c m$ 时要小心爆 $l o n g <mtext> </mtext> l o n g$ , 要转化为 $d o u b l e$ 进行运算 .

总结: 对暴搜的优化主要包括

使搜索规模消减: 体现在 优化2,3 .
使搜索过程尽早结束, 体现在 优化1,剪枝1 .

$实现部分$
没什么好说的 …

#include<cstdio>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 40005;

int cnt;

ll a;
ll b;
ll Tmp_1;
ll A[maxn];
ll B[maxn];

bool Used[maxn];

ll Gcd(ll a, ll b){ return !b?a:Gcd(b, a%b); }
ll Lcm(ll a, ll b){ return a/Gcd(a, b) * b; }

void DFS(ll sum){
        if(sum > b) return ;
        if(sum) A[++ cnt] = sum;
        DFS(sum*10 + 6);
        DFS(sum*10 + 8);
}

void DFS_2(int k, bool opt, ll sum){
        if(k == cnt+1){
                if(sum == 1) return ;
                if(opt & 1) Tmp_1 += b/sum - (a-1)/sum;
                else Tmp_1 -= b/sum - (a-1)/sum;
                return ;
        }
        if(sum > b) return ;
        DFS_2(k+1, opt, sum);
        sum = sum/Gcd(sum, B[k]);
        if((double)sum*B[k] <= b) DFS_2(k+1, opt^1, sum*B[k]);
}

int main(){
        scanf("%lld%lld", &a, &b);
        DFS(0);
        std::sort(A+1, A+cnt+1);
        for(reg int i = 1; i <= cnt; i ++){
                if(Used[i]) continue ;
                for(reg int j = i+1; j <= cnt; j ++)
                        if(A[j]%A[i] == 0) Used[j] = 1;
        }
        int tmp = 0;
        for(reg int i = cnt; i >= 1; i --){
                if(Used[i]) continue ;
                if(A[i] > b/3) Tmp_1 += b/A[i] - (a-1)/A[i];
                else B[++ tmp] = A[i];
        }
        cnt = tmp;
        DFS_2(1, 0, 1);
        printf("%lld\n", Tmp_1);
        return 0;
}