题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。

每组数据输入$n(1 \leq n \leq 10^9)$和$m(1 \leq m \leq 10^9)$。

输出$n,2n,3n,…,mn$中末尾零最多的数。如果有多个符合要求的数，输出其中最大的。

输入样例

10
6 11
5 43
13 5
4 16
10050 12345
2 6
4 30
25 10
2 81
1 7

输出样例

60
200
65
60
120600000
10
100
200
100
7

算法

枚举

根据数据范围，$2^{30} \gt 10^9$，$5^{13} \gt 10^9$。考虑到某个数的尾随零个数取决于它因子$2$个数和因子$5$个数的较小值，因此对于给定的$n$，我们可以先在$O(logn)$的复杂度下求出$n$中的因子$2$个数$cnt_2$，$n$中的因子$5$个数$cnt_5$。然后枚举因子$2$和$5$的个数$i$和$j$，对于$2^i \times 5^j \leq m$的$(i,j)$：

1. 如果$min(cnt_2+i,cnt_5+j)$变大了，直接更新答案为$n \times \lfloor \frac{m}{2^i \times 5^j} \rfloor \times 2^i \times 5^j$。
2. 如果$min(cnt_2+i,cnt_5+j)$不变，就只有在$n \times \lfloor \frac{m}{2^i \times 5^j} \rfloor \times 2^i \times 5^j$比当前答案大时才更新答案。

其中$\lfloor . \rfloor$表示对$.$向下取整，之所以要用$m$除以$2^i \times 5^j$，就是为了在$n$的倍数$k$包含足够尾随零且$kn \leq m$的情况下能够得到更大的数。

复杂度分析

时间复杂度

每个$case$需要先计算$n$中因子$2$和因子$5$的数量，时间复杂度为$O(log_2n+log_5n)$。然后双重循环枚举$m$中因子$2$和因子$5$的数量，时间复杂度为$O(log_2mlog_5m)$，大概为$O((logm)^2)$。$T$个$case$总的时间复杂度为$O(T(logn+(logm)^2))$

空间复杂度

仅使用了有限几个变量，额外空间复杂度为$O(1)$。

$python$代码

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    x = n
    cnt2, cnt5 = 0, 0
    while x % 2 == 0:
        x >>= 1
        cnt2 += 1
    while x % 5 == 0:
        x //= 5
        cnt5 += 1
    ans = 0
    cnt = min(cnt2, cnt5)
    for i in range(31):
        for j in range(14):
            num = 2**i*5**j
            if num <= m:
                res = m//num*num*n
                if cnt < min(cnt2 + i, cnt5 + j):
                    cnt = min(cnt2 + i, cnt5 + j)
                    ans = res
                elif cnt == min(cnt2 + i, cnt5 + j):
                    if res > ans:
                        ans = res
    if cnt == 0:
        ans = n*m
    print(ans)