Once upon a time, there was a curious mathematician named Alice. She loved playing with numbers. One day, she encountered a challenge. In this challenge, she had to assume that a magical box containing numbers from \(1\) to \(N\) existed, and she had to select \(M\) distinct numbers from this box such that the sum of their divisors was the greatest, and then report this maximum possible sum of their divisors.
Alice had to solve this puzzle multiple times for various values of \(N\) and \(M\) since she was quite busy she asked for your help.
The rules of the challenge are:
- You have to answer \(T\) such puzzles.
- For each puzzle, you are provided with two integers, \(N\) and \(M\).
- Your task is to determine the maximum total sum of the divisors of \(M\) distinct numbers from \(1\) to \(N\).
Input format
- The first line contains a single integer \(T\), which denotes the number of puzzles.
- Each of the next \(T\) lines contains two integers \(N\) and \(M\).
Output format
For each puzzle, print in a new line the maximum total sum of the divisors of \(M\) distinct numbers from \(1\) to \(N\).
Constraints
1 7 3
27
For puzzle \(1\):
- N = 7
- M = 3
In this, you need to to choose 3 numbers from 1 to 7 such that there total sum of the divisors is the maximum possible. You can pick numbers 4, 6, and 7 and get the total sum of divisors as 27. This is because:
- divisor of 1 = 1
- divisors of 2 = 1, 2
- divisors of 3 = 1, 3
- divisors of 4 = 1, 2, 4
- divisors of 5 = 1, 5
- divisors of 6 = 1, 2, 3, 6
- divisors of 7 = 1, 7
therefore we can get the maximum total sum of divisors by choosing 4, 6 & 7. Thus, the answer is ((1+2+4) + (1+2+3+6) + (1+7)) = 27
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor