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
rishabh_1997:
2016-07-10 12:07:53
Learnt some new things, use modular exponentiation for faster power calculation
|
|
newbie:
2015-11-14 20:57:43
easy one just simple logic is enough :) |
|
Malinga:
2015-01-15 07:35:44
consider ** times=b/i - (a-1)/i ** caused me two WA.. |
|
Yashpal:
2014-12-30 08:36:52
O(sqrt(b)+sqrt(a))logn giving AC in 15 Sec .. :(
|
|
Bharath Reddy:
2014-09-29 16:05:00
Got AC with a generic implementation.
|
|
oye lakshman help plz:
2014-06-29 03:04:54
@lakshman is this the correct ans 299384888 also is there any fast algo for powersum
|
|
[Lakshman]:
2014-06-29 02:59:39
@crazzysuarez Have you tried this case
|
|
tyson:
2014-06-28 20:42:41
getting WA plz provide with some test case
|
|
Rishav Goyal:
2014-04-20 09:46:59
yay :DDDDDD finalyy AAAcCCCCC :) |
|
Prakhar Gupta:
2014-01-22 14:51:06
nlog(n) always giving TLE on running (10)
|
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 |