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$。

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *