IITD4 - Divisor Summation Powered
Define F(n, k) = Sum of kth powers of all divisors of n, so for example F(6, 2) = 1^2 + 2^2 + 3^2 + 6^2 = 50
Define further G(a, b, k) as: Sum of F(j, k) where j varies from a to b both inclusive.
Your task is to find G(a, b, k) given a, b and k.
As values of G can get very large, you only need to output the value of G(a, b, k) modulo 10^9+7.
Input
First line of input file contains a single integer T - denoting the number of test cases.
The follow description of T test cases. Each test case occupies exactly one line which contains three space separated integers a, b and k.
Output
Output your result for each test case in a new line.
Sample
Input: 2 2 2 1 1 3 2 Output: 3 16
Description of Sample
In case 1, we are to find sum of divisors of 2. which is nothing but 1 + 2 = 3.
In case 2, we are to find sum of squares of divisors of 1, 2 and 3. So for 1 sum is = 1. For 2 sum is = 1^2 + 2^2 = 5. For 3 sum is = 1^2 + 3^2=10. So answer is 16.
Constraints
1 <= a <= b <= 10^5
1 <= k <= 10^5
Number of test cases <= 20
hide comments
Rohan Garg:
2013-12-31 21:16:45
Java time limit should be increased. The same solution in C passed 7 seconds faster than the slowest solution in C/C++. |
|
Divanshu:
2013-03-21 13:49:51
Optimisations required to AC !
|
|
praveen123:
2013-02-11 22:14:44
accepted after a lot of TLE's :) |
|
god_father:
2013-01-23 20:27:09
really good question no need of any precompution... |
|
Vikas Kushwaha:
2012-12-30 07:17:48
a very good problem.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-06 13:19:56
easy, no precomputation or memoization needed to get AC, my semi-bruteForce program got AC! |
|
blashyrkh:
2011-08-25 11:51:17
Not a lot really. Memorization of some intermediate results is enough to get AC.
|
|
sandeep pandey:
2011-04-25 20:20:44
nice problem.
|
Added by: | Nikhil Garg |
Date: | 2010-10-15 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC VB.NET |
Resource: | own problem, used for IIT Delhi ACM ICPC provincial contest 2010 |