Codechef September long challenge 2021 | Minimum Digit Sum 2 Solution

 

Codechef September long challenge 2021 | Minimum Digit Sum 2 Solution

• 
  

This problem is similar to the problem “MNDIGSUM”. The only differences are in the constraints and in the input format. In this problem the range for the base BB is [2,R][2,R], the value of nn can be upto 10121012 and the total number of queries is at most 300300. The differences are described in bold.

Let f(n,B)f(n,B) be the sum of digits of the integer nn when written in base BB.

Given QQ queries, each consisting of two integers nn and rr. Find the value of BB corresponding to which f(n,B)f(n,B) is minimum for all 2≤B≤r2≤B≤r. If there are multiple such values, you can print any of them.

Input Format

• The first line contains in single integer QQ, the number of queries
• Each of the next QQ lines contain two space separated integers nn and rr respectively.

Output Format

• For each query (n r) find the value of the base BB that lies within [2,r][2,r] such that f(n,B)f(n,B) is minimum.

Constraints

• 1≤Q≤3001≤Q≤300
• 2≤n≤10122≤n≤1012
• 2≤r≤10122≤r≤1012

Subtasks

Subtask #1 (50 points): original constraints

This problem is worth a total of 50 points and is meant to be complementary to the problem “MNDIGSUM” (also worth 50 points) which is very similar to this problem, but has slightly different constraints.

Sample Input 1 

3
216 7
256 4
31 5

Sample Output 1 

6
2
5

Explanation

Test case 11: We have f(216,2)=f(216,3)=4f(216,2)=f(216,3)=4, f(216,4)=6f(216,4)=6, f(216,5)=8f(216,5)=8, f(216,6=1)f(216,6=1) and finally f(216,7)=12f(216,7)=12. Clearly the minimum is obtained when B=6B=6.

Test case 22: Note that f(256,2)=f(256,4)f(256,2)=f(256,4) = 22, therefore both the answers 22 and 44 will be considered correct.

Test case 33: f(31,3)=f(31,5)=3f(31,3)=f(31,5)=3 and f(31,4)=7f(31,4)=7, therefore both the answers 33 and 55 will be considered correct.