Count Good Numbers

The definition looks like it wants prime factorization, but that is bait. For $r\le 10^{18}$, factoring every number in a range would be a disaster, and also completely unnecessary.

A number is bad if some prime in its factorization has one digit.

The one-digit primes are only:

$2,3,5,7$

So a number is good iff it is not divisible by any of those four primes. That's the entire trick.

For example:

• $111 = 3\cdot 37$ is bad because it is divisible by $3$.
• $343 = 7^3$ is bad because it is divisible by $7$.
• $1111 = 11\cdot 101$ is good because neither prime factor is one-digit.
• $43$ is good because $43$ itself has two digits.

So we need to count numbers in $[l,r]$ not divisible by $2$, $3$, $5$, or $7$.

Prefix counting

Let $f(n)$ be the number of integers from $1$ to $n$ that are good. Then the answer for a test case is:

$f(r)-f(l-1)$

Now we only need a fast way to compute $f(n)$.

Inclusion-exclusion

Start with all $n$ numbers from $1$ to $n$.

Remove numbers divisible by $2$, $3$, $5$, or $7$.

But if we subtract numbers divisible by $2$ and numbers divisible by $3$, then numbers divisible by $6$ got subtracted twice, so we add them back. Same old inclusion-exclusion stuff.

For every subset of primes $\{2,3,5,7\}$:

• multiply the chosen primes into $d$,
• count how many numbers are divisible by $d$: $\left\lfloor\frac{n}{d}\right\rfloor$,
• add it if the subset size is even,
• subtract it if the subset size is odd.

The empty subset has product $1$ and even size, so it contributes $+n$.

So:

$$f(n)=\sum_{S\subseteq\{2,3,5,7\}}(-1)^{|S|}\left\lfloor\frac{n}{\prod_{p\in S}p}\right\rfloor$$

There are only $16$ subsets, so this is tiny. Like, embarrassingly tiny. Codeforces gave us $10^{18}$ and we bonk it with sixteen divisions.

What about $1$?

The input always has $l\ge 2$. Our prefix formula counts $1$ as good, because it is not divisible by $2,3,5,7$. That is fine. When answering $f(r)-f(l-1)$, this behaves correctly, and for ranges starting at $2$, it subtracts away the $1$.

Complexity

For each test case, we check $16$ subsets.

Time complexity: $O(16t)$, basically $O(t)$.

Memory complexity: $O(1)$.