CF2153E Zero Trailing Factorial

For all positive integers $ x\ge 1 $ and $ k\ge 2 $ , let $ v_k(x!) $ denote the number of trailing zeros in the base- $ k $ representation of $ x! = x\cdot (x-1)\cdot \ldots \cdot 1 $ . Formally, $ v_k(x!) $ is defined as the largest integer $ i $ such that $ k^i $ divides $ x! $ . For a prime number $ p $ , we can calculate $ v_p(x!) = \sum\limits_{j=1}^\infty \left\lfloor \frac{x}{p^j}\right\rfloor $ $ ^{\text{∗}} $ . If $ k $ is not prime, write its prime factorization as $ k = \prod p_i^{e_i} $ , where $ p_i $ are distinct prime factors and $ e_i $ are their corresponding exponents. Then, $$$ v_k(x!) = \min\limits_i \left\lfloor \frac{v_{p_i}(x!)}{e_i}\right\rfloor. $$$ For any two positive integers $ a $ and $ b $ , and any integer $ k\ge 2 $ , the weight of the pair $ (a, b) $ with respect to $ k $ , denoted by $ w_k(a, b) $ , is defined as $$$ w_k(a, b) = \begin{cases}\min(v_k(a!), v_k(b!)) & \text{if }v_k(a!)\neq v_k(b!)\text{;}\\10^{100} & \text{otherwise.}\end{cases} $$$ Next, define $ f_m(a, b) $ as the minimum weight of the pair $ (a, b) $ with respect to $ k $ , taken over all integers $ k $ with $ 2\le k\le m $ : $$$ f_m(a, b)=\min\limits_{2\le k\le m}w_k(a, b). $$$ You are given two integers $ n $ and $ m $ . Your task is to compute the sum of $ f_m(x, n) $ over all positive integers $ x $ less than $ n $ : $$$ \sum_{1\le x\le n - 1} f_m(x, n). $$$ It can be shown that under the given constraints, the result is strictly less than $ 10^{100} $ . $ ^{\text{∗}} $ $ \lfloor y\rfloor $ denotes the [floor](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) of $ y $ , which is the greatest integer less than or equal to $ y $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first and only line of each test case contains two integers $ n $ and $ m $ ( $ 2\le n\le m\le 10^7 $ ) — the parameters of the function. Note that there are no constraints on the sum of $ n, m $ over all test cases.

For each test case, output a single integer representing $ \sum\limits_{1\le x\le n - 1} f_m(x, n) $ .

In the first test case, consider $ k = 3\le 5 $ : - $ v_3(1!) = v_3(2!) = 0 $ , since $ 3 $ does not divide both $ 1 $ and $ 2 $ . - $ v_3(3!) = v_3(6) = 1 $ , since $ 3 $ divides $ 6 $ , but $ 3^2 = 9 $ does not. Therefore, $ w_3(1, 3) = w_3(2, 3) = \min(0, 1) = 0 $ . It can be shown that this is the minimum weight across all $ 2\le k\le 5 $ , so $ f_5(1, 3) = f_5(2, 3) = 0 $ . In the second test case, it can be shown that $ f_7(1, 6) = f_7(2, 6) = f_7(3, 6) = f_7(4, 6) = 0 $ . For $ f_7(5, 6) $ , we consider $ k = 6\le 7 $ : - $ v_6(5!) = v_6(120) = 1 $ , since $ 6 $ divides $ 120 $ , but $ 6^2 = 36 $ does not. - $ v_6(6!) = v_6(720) = 2 $ , since $ 6^2 = 36 $ divides $ 720 $ , but $ 6^3 = 216 $ does not. Therefore, $ w_6(5, 6) = \min(1, 2) = 1 $ . It can be shown that this is the minimum weight across all $ 2\le k\le 7 $ , so $ f_7(5, 6) = 1 $ . Note: choosing $ k = 7 \le 7 $ does not work, because $ v_7(5!) = v_7(6!) = 0 $ , so $ w_7(5, 6) = 10^{100} $ . In the third test case, it can be shown that $ f_{10}(1, 6) = f_{10}(2, 6) = f_{10}(3, 6) = f_{10}(4, 6) = 0 $ . For $ f_{10}(5, 6) $ , we consider $ k = 9\le 10 $ : - $ v_9(5!) = v_9(120) = 0 $ , since $ 9 $ does not divide $ 120 $ . - $ v_9(6!) = v_9(720) = 1 $ , since $ 9 $ divides $ 720 $ , but $ 9^2 = 81 $ does not. Therefore, $ w_9(5, 6) = \min(0, 1) = 0 $ . It can be shown that this is the minimum weight across all $ 2\le k\le 10 $ , so $ f_{10}(5, 6) = 0 $ .