Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef and Abhishek are two friends. Abhishek really appreciates Chef's skills and wants to learn the secret formula behind Chef's tasty dishes. Chef will tell his secret formula only to a 
competent person. So to check Abhishek's competency, Chef asked him to solve the following problem.  
  
Find the number of integers between 0 and N (inclusive) such that the product of digits of the integer is greater than or equal to K!, where K is the number of digits present in the integer.  
  
Example: Consider N = 1000. 
The only digit present in the integer 0 is 0. So the product of digit is also 0 and 1! = 1. So 0 will be not counted in the answer because 0 \ngtr 1.
The digits present in the integer 25 are 2, 5. So the product of digits is (2 \cdot 5) = 10 and 2 ! = 2. So 25 will be counted in the answer because  10 ≥ 2. 
The digits present in the integer 11 are 1, 1. So the product of digits is (1 \cdot 1) = 1 and 2 ! = 2. So 11 will be not counted in the answer because 1 \ngtr 2.
The digits present in the integer 157 are 1, 5, 7. So the product of digits is (1 \cdot 5 \cdot 7) = 35 and  3! = 6. So 157 will be counted in the answer because 35 ≥ 6. 

Since Abhishek is a lazy person, he wants your help to solve the problem.  

Note: K! represents the factorial of K and K! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (K-1) \cdot K .  
  
------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a single integer N.

------ Output Format ------ 

For each test case, output in a single line the answer for given integer N

------ Constraints ------ 

$1 ≤ T ≤ 10145$
$0 ≤ N ≤ 10^{100}$

------ subtasks ------ 

Subtask #1 (10 points):     
$1 ≤ T ≤ 200$   
$0 ≤ N ≤ 44000000$  

Subtask #2 (90 points): Original constraints 

----- Sample Input 1 ------ 
3
13
54
198
----- Sample Output 1 ------ 
11
48
159
----- explanation 1 ------ 
Test case $1$: The only one-digit number that will not be included in the answer is $0$. The two-digit numbers that will not be included in the answer are $10, 11$ because their product of digits is less than $2! = 2$. So the answer is $= 14 - 1 - 2 = 11$. 
  
Test case $3$:   
- The one-digit number that will not be counted in the answer is $0$. 
- The two-digit digit numbers that will not be counted in the answer are $10, 11$, $20, 30$, $40, 50, 60,$ $70, 80, 90$ because their product of digits is less than $2! = 2$. 
- The three-digit numbers that will not be counted in the answer are $100$, $101, 102,$ $103, 104, 105$, $106, 107, 108$, $109, 110, 111,$ $112, 113, 114,$ $115, 120$,$ 121,$ $122, 130, 131,$ $140, 141,      
150,$ $151, 160, 170$, $180, 190$ because their product of digits is less than $3! = 6$.  
So the answer is $= 199 - 1 - 10 - 29 = 159$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Sorting

Mathematics

Complete search


Solutions:
import sys
import bisect
NN = 27
pw = [[1] * NN for i in range(NN)]
(fac, cnt, adj, sz) = ([1] * NN, [0] * NN, [[] for i in range(NN)], [0] * NN)

def dfs(val, num, ed):
	if val == 0 and num > 0:
		return 0
	if val == 0:
		if ed != 1:
			return 0
		(N, M, v) = (0, 1, 1)
		for i in range(10):
			N += cnt[i]
			M *= fac[cnt[i]]
			v *= pw[i][cnt[i]]
		NUM = fac[N] // M
		adj[N].append([v, NUM])
		return 0
	if pw[val][num] < ed:
		return 0
	for i in range(num + 1):
		v = pw[val][i]
		cnt[val] = i
		dfs(val - 1, num - i, (ed + v - 1) // v)

def CLC(u):
	adj[u] = sorted(adj[u])
	ed = 0
	for i in range(1, len(adj[u])):
		if adj[u][i][0] == adj[u][ed][0]:
			adj[u][ed][1] += adj[u][i][1]
		else:
			adj[u][ed + 1] = adj[u][i]
			ed += 1
	sz[u] = ed + 1
	for i in range(ed - 1, -1, -1):
		adj[u][i][1] += adj[u][i + 1][1]
a = [0] * NN

def seg(u, V):
	if u == 0:
		if V < 2:
			return 1
		else:
			return 0
	it = bisect.bisect_left(adj[u], [V, 0], lo=0, hi=sz[u])
	if it == sz[u]:
		return 0
	return adj[u][it][1]

def calc(n):
	L = 0
	while n > 0:
		a[L] = n % 10
		L += 1
		n //= 10
	ans = 0
	for i in range(1, L):
		ans += seg(i, fac[i])
	V = fac[L]
	for i in range(L - 1, -1, -1):
		for j in range(1, a[i]):
			ans += seg(i, (V + j - 1) // j)
		if a[i] == 0:
			break
		V = (V + a[i] - 1) // a[i]
		if i == 0:
			if V == 1:
				ans += 1
	return ans
for i in range(NN):
	for j in range(1, NN):
		pw[i][j] = pw[i][j - 1] * i
for i in range(1, NN):
	fac[i] = fac[i - 1] * i
for i in range(1, NN):
	CNT = 0
	if i > 10:
		dfs(9, i, fac[i])
	else:
		dfs(9, i, 1)
	CLC(i)
t = int(input())
for i in range(t):
	n = int(input())
	n = min(n, 10 ** 22 - 1)
	print(min(n, calc(n)))


import sys
D = 22
dp = [dict() for _ in range(D)]
dp[0][1] = 1
for d in range(D - 1):
	for (product, freq) in dp[d].items():
		for nxt in range(1, 10):
			dp[d + 1][product * nxt] = freq + dp[d + 1].get(product * nxt, 0)
(products, frequencies) = ([list() for _ in range(D)], [list() for _ in range(D)])
sum = 0
for d in range(D):
	dp[d] = dict(sorted(dp[d].items()))
	tot = 0
	for freq in dp[d].values():
		tot += freq
	for (prod, freq) in dp[d].items():
		x = dp[d][prod]
		dp[d][prod] = tot
		tot -= x
	(products[d], frequencies[d]) = (list(dp[d].keys()), list(dp[d].values()))
	sum += len(dp[d])

def countNumsGreater(d, target):
	(lo, hi) = (0, len(products[d]) - 1)
	if products[d][hi] < target:
		return 0
	while lo < hi:
		mid = (lo + hi) // 2
		if products[d][mid] >= target:
			hi = mid
		else:
			lo = mid + 1
	return frequencies[d][hi]

def good(N):
	N = str(N)
	(fact, prod) = (1, 1)
	for d in range(len(N)):
		fact *= d + 1
		prod *= ord(N[d]) - ord('0')
	return prod >= fact

def brute(N):
	N = int(N)
	ans = 0
	for x in range(1, 1 + N):
		if good(x):
			ans += 1
	return ans
T = int(input())
MAX = 10 ** (D - 1)
for _ in range(T):
	N = int(input())
	if N > MAX:
		N = MAX
	N = str(N)
	(ans, fact) = (0, 1)
	for d in range(1, len(N)):
		fact *= d
		ans += countNumsGreater(d, fact)
	fact *= len(N)
	product = 1
	for p in range(len(N)):
		di = ord(N[p]) - ord('0')
		if di == 0:
			break
		for digit in range(1, di):
			tmpProd = product * digit
			ans += countNumsGreater(len(N) - p - 1, (fact + tmpProd - 1) // tmpProd)
		product *= di
	if good(N):
		ans += 1
	sys.stdout.write(str(ans) + '\n')


import heapq
import sys
import random
fac = []
fac.append(1)
for n in range(1, 31):
	fac.append(fac[-1] * n)

class Element:
	__slots__ = ['pairs', 'prefix_sum']

	def __init__(self, pairs):
		heap = []
		result = []
		len_pairs = len(pairs)
		for d in range(1, 10):
			value = (pairs[0][0] * d, d, 0)
			heapq.heappush(heap, value)
		while heap:
			(_, d, i) = heapq.heappop(heap)
			(key, value) = pairs[i]
			key *= d
			if len(result) and result[-1][0] == key:
				result[-1] = (key, result[-1][1] + value)
			else:
				result.append((key, value))
			if i + 1 < len_pairs:
				heapq.heappush(heap, (pairs[i + 1][0] * d, d, i + 1))
		self.pairs = result
		self.prefix_sum = [0]
		for (key, value) in self.pairs:
			self.prefix_sum.append(self.prefix_sum[-1] + value)
dp = []
dp.append(Element([(1, 1)]))
for i in range(1, 22):
	dp.append(Element(dp[-1].pairs))

def count(prefix, num_digits, fac_k):
	if prefix == 0:
		return 0
	if num_digits == 0:
		if prefix >= fac_k:
			return 1
		else:
			return 0
	d = dp[num_digits - 1]
	pairs = d.pairs
	if pairs[0][0] * prefix >= fac_k:
		return d.prefix_sum[-1]
	if pairs[-1][0] * prefix < fac_k:
		return 0
	l = 0
	r = len(pairs) - 1
	while r - l > 1:
		m = (l + r) // 2
		if pairs[m][0] * prefix >= fac_k:
			r = m
		else:
			l = m
	return d.prefix_sum[-1] - d.prefix_sum[l + 1]

def solve():
	n_str = input()
	n_len = len(n_str)
	answer = 0
	for num_digits in range(1, 22):
		if num_digits > n_len:
			break
		if num_digits < n_len:
			answer += count(1, num_digits, fac[num_digits])
		if num_digits == n_len:
			prefix = 1
			for i in range(n_len):
				d = int(n_str[i])
				for k in range(1, d):
					answer += count(prefix * k, num_digits - i - 1, fac[n_len])
				prefix = prefix * d
				if num_digits - i - 1 == 0:
					answer += count(prefix, num_digits - i - 1, fac[n_len])
				if prefix == 0:
					break
	print(answer)
t = int(input())
while t > 0:
	t -= 1
	solve()