DivisorDilemma

4.4

7 votes
Advanced Data Structures, Binary Search, Number Theory, Segment Trees, Data Structures, Math
Problem

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:

  1. You have to answer T such puzzles.
  2. For each puzzle, you are provided with two integers, N and M.
  3. 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

1T1061MN2×106

 

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?