KPOWERSUM - Kth Power Summation
Leeana Learned Few New Things Few Days Ago , Like:
1) Find The Summation Of Divisors.
2) Modular Arithmetic
So Now Her Uncle Gave Her A Task.
Task Is: You Will Be Given A Number(N) And Another Number(K). Now You Have To Find Kth Power Summation Of Divisors Of N.
Summation Of All Divisors Of N Will Be Huge, So You Have To Print The Summation Module (M=1000000007).
Like: Divisors Of 6 is: ( 1 2 3 6 ) And K = 2.
so, summation is: 1^K+2^K+3^K+6^K = 1^2 + 2^2 + 3^2 + 6^2= 1+4+9+36 = 50%1000000007=50
Leeana Thinks That You Are A Great Programmer, So She Needs Your Help. Can You Help Her??? :D :D :D
Input
Input Starts With An Integer T (≤ 500), Denoting The Number Of Test Cases. Each Case Contains An Integer N (1 ≤ N ≤ 1015) And An Integer K (1 ≤ K ≤ 105) Denoting The Power Of Divisors.
Output
For Each Test Cases, Print The Case Number And The Kth Power Summation Of Divisors Of N Module 1000000007. After Each Case Print A New Line. See Sample Input And Output For Better Explanation.
Example
Input: 4 6 2 6 1 6 4 6 3
Output: Case 1: 50 Case 2: 12 Case 3: 1394 Case 4: 252
#Extra_Challenge: N<=10^18, T<=1000 TL: 1s
hide comments
shubham_001:
2018-09-06 20:02:08
Giving TLE , can you tell expected time complexity? |
|
bdezso:
2018-09-06 07:48:08
Could you check my last submission? :/ TLE with formula.
|
|
[Lakshman]:
2018-09-05 11:28:26
Not sure why I am getting wrong answer now. @RaYHan may I have a test case where my new code is failing.
|
|
Kata:
2018-09-05 10:54:51
Did you fixed the test cases for judge, not just the sample? I do not think my code was wrong.
|
|
chhavi96:
2018-09-03 17:06:59
time limit is very strict....
|
|
rayhan50001:
2018-09-03 16:00:59
oh sorry. thank you. :( |
|
bdezso:
2018-09-03 15:23:01
yes, test cases are wrong.
|
|
[Lakshman]:
2018-09-03 11:04:03
Are you sure test cases are correct?. In sample test cases T should be 4, not 2.
|
Added by: | RaYHan |
Date: | 2018-09-02 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own Problem |