IITD4 - Divisor Summation Powered

no tags 

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 & 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 Format:


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 & k.

Output Format:


Output your result for each test case in a new line.


Sample Input File:

2
2 2 1
1 3 2

Sample Output File:

3
16


Description of sample output:

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 & 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 ans 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
AC 2.03s in third attempt , after 2 TLEs.
A much recommended problem.

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 .. :(
Any sort of Optimization ??

Last edit: 2014-12-30 08:37:09
Bharath Reddy: 2014-09-29 16:05:00

Got AC with a generic implementation.
No need of code optimizations. A good algorithm is enough
Hint: Look at the constraints closely :)

Last edit: 2014-09-29 16:11:46
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
here is my code
https://ideone.com/mz3gZn
kindly help me

Last edit: 2014-06-29 03:06:12
[Lakshman]: 2014-06-29 02:59:39

@crazzysuarez Have you tried this case
1
1 100000 9999

Last edit: 2014-06-29 03:02:14
tyson: 2014-06-28 20:42:41

getting WA plz provide with some test case
@nikhil sub id 11848600

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)

Last edit: 2014-02-23 14:08:36

Added by:Nikhil Garg
Date:2010-10-15
Time limit:0.530s
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