The Almost Lucky Numbers

题目描述

A lucky number is a number whose decimal representation contains only the digits $4$ and $7$. An almost lucky number is a number that is divisible by a lucky number.

For example, $14, 36$ and $747$ are almost lucky, but $2$ and $17$ are not. Note that a number can be both lucky and almost lucky at the same time (for example, $747$).

You are given long longs $a$ and $b$. Return the number of almost lucky numbers between $a$ and $b$, inclusive.

题意概述

只由$4$和$7$组成的数叫做 lucky number，能被 lucky number 整除的数叫做 almost lucky nunber，问区间$[a, b]$中有多少个 almost lucky number。

数据范围：$1 \le a \le b \le 10^{10}$。

算法分析

可以发现，lucky number 的个数不会很多，而且若某个 lucky number 是另一个 lucky number 的倍数，则这个 lucky number 可以忽略。

易知只需分别求出$[1, a-1]$和$[1, b]$中 almost lucky number 的个数，两者相减即可得到答案。

下面来研究怎样求出$[1, n]$中 almost lucky number 的个数。对于在$[1, n]$中的某一个 lucky number（设为$p$），区间$[1, n]$中能被它整除的数的个数为$\left\lfloor {n \over p} \right\rfloor$。将这些数删去后，对于在$[1, n]$中的某两个 lucky number（设为$p, q$），区间$[1, n]$中能被它们整除的数的个数为$\left\lfloor {n \over LCM(p, q)} \right\rfloor$。因为这些数在之前被删去了两次，所以要将这些数加上。以此类推，利用暴力容斥即可解决此题。

有两个小优化：当某个$LCM$大于$n$时，这个$LCM$可以忽略；从大到小枚举 lucky number，使得$LCM$可以很快超过$n$。