Make It Round (Codeforces 1759D)
Tags: Others, number theory

Inflation has occurred in Berlandia, so the store needs to change the price of goods.The current price of good $$$n$$$ is given. It is allowed to increase the price of the good by $$$k$$$ times, with $$$1 \le k \le m$$$, k is an integer. Output the roundest possible new price of the good. That is, the one that has the maximum number of zeros at the end.For example, the number 481000 is more round than the number 1000010 (three zeros at the end of 481000 and only one at the end of 1000010).If there are several possible variants, output the one in which the new price is maximal.If it is impossible to get a rounder price, output $$$n \cdot m$$$ (that is, the maximum possible price).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases in the test.Each test case consists of one line.This line contains two integers: $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$). Where $$$n$$$ is the old price of the good, and the number $$$m$$$ means that you can increase the price $$$n$$$ no more than $$$m$$$ times.

Output: For each test case, output on a separate line the roundest integer of the form $$$n \cdot k$$$ ($$$1 \le k \le m$$$, $$$k$$$ — an integer).If there are several possible variants, output the one in which the new price (value $$$n \cdot k$$$) is maximal.If it is impossible to get a more rounded price, output $$$n \cdot m$$$ (that is, the maximum possible price).

Note: In the first case $$$n = 6$$$, $$$m = 11$$$. We cannot get a number with two zeros or more at the end, because we need to increase the price $$$50$$$ times, but $$$50 > m = 11$$$. The maximum price multiple of $$$10$$$ would be $$$6 \cdot 10 = 60$$$.In the second case $$$n = 5$$$, $$$m = 43$$$. The maximum price multiple of $$$100$$$ would be $$$5 \cdot 40 = 200$$$.In the third case, $$$n = 13$$$, $$$m = 5$$$. All possible new prices will not end in $$$0$$$, then you should output $$$n \cdot m = 65$$$.In the fourth case, you should increase the price $$$15$$$ times.In the fifth case, increase the price $$$12000$$$ times.

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

Sample Outputs:
60
200
65
60
120600000
10
100
200
100
7

Solution (Python):
import sys
input = sys.stdin.readline
result = []
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    (c2, c5) = (0, 0)
    N = n
    while n % 2 == 0:
        c2 = c2 + 1
        n //= 2
    while n % 5 == 0:
        c5 = c5 + 1
        n //= 5
    ans = 1
    while c2 < c5 and ans * 2 <= m:
        ans *= 2
        c2 = c2 + 1
    while c5 < c2 and ans * 5 <= m:
        ans *= 5
        c5 = c5 + 1
    while ans * 10 <= m:
        ans *= 10
    ans = m // ans * ans
    print(ans * N)

Solution (Python):
import sys
input = sys.stdin.readline

class Solver:

    def solve(self, n, m):
        (count_2, count_5) = self.factorize2_5(n)
        if count_2 > count_5:
            base = 5
        elif count_5 > count_2:
            base = 2
        else:
            base = 10
        missing = max(count_2, count_5) - min(count_2, count_5)
        if base > m:
            return n * m
        num = 1
        while missing > 0 and num * base <= m:
            num *= base
            missing -= 1
        while num * 10 <= m:
            num *= 10
        base = 10
        while num * base > m:
            base -= 1
        num *= base
        return num * n

    def factorize2_5(self, n):
        counts = [0, 0]
        while n % 2 == 0:
            n /= 2
            counts[0] += 1
        while n % 5 == 0:
            n /= 5
            counts[1] += 1
        return counts
if __name__ == '__main__':
    solver = Solver()
    t = int(input())
    for i in range(t):
        (n, m) = list(map(int, input().split()))
        result = solver.solve(n, m)
        print(result)

Solution (Python):
import collections
import heapq
import sys
import math
import bisect
import os
from io import BytesIO, IOBase
input = sys.stdin.readline

def solve():
    (n, m) = list(map(int, input().split()))
    nn = n
    while n % 10 == 0:
        n //= 10
    tot = 1
    while n % 5 == 0 and tot * 2 <= m:
        tot *= 2
        n //= 5
    while n % 2 == 0 and tot * 5 <= m:
        tot *= 5
        n //= 2
    while tot * 10 <= m:
        tot *= 10
    print(nn * tot * (m // tot))
if __name__ == '__main__':
    for i in range(int(input())):
        solve()