A strange sum | Practice Problems

A strange sum

★★★★★

3.4

16 votes

Lagrange Interpolation, Implementation, Linear Algebra, C++, Number theory, Optimization, Math

Details

Submissions

Discussion

Editorial

Problem

You are given 2 integers $N$ and $M$ . Let $g(i)$ denotes the number of divisors of $i$ , that is count of positive numbers dividing $i$ . Your task is to find the sum:

Since the answer can be very large, you are required to print it modulo $(10^9 + 7)$

Input format

The first line contains a single integer $T$ denoting the number of test cases.
For each test case:
The first and only line contains 2 space-separated integers $N$ and $M$ .

Output format

For each test case, print the sum modulo $(10^9 + 7)$ in a separate line.

Constraints

$1 \le T \le 8 \\ 1 \leq N \leq 10^9 \\ 0 \leq M \leq 1000$

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In the first test case, we have $N = 4, M = 2$ . Now, $g(1) = 1, g(2) = 2, g(3) = 2, g(4) = 3$ . This is because:

1 is divisible by only 1.
2 is divisible by 1 and 2.
3 is divisible by 1 and 3.
4 is divisible by 1, 2 and 4.

So, $\sum\limits_{i=1}^{4} i^M * g(i)$ = $1*1 + 2^2*2 + 3^2*2 + 4^2*3$ = $75$ .

In the second test case, we have $N = 1$ . So, sum is $1$ .