SPOJ.com - Problem KPOWERSUM

KPOWERSUM - Kth Power Summation

#math #number-theory #modulo-1

Leeana Learned Few New Things Few Days Ago, Like:

Find The Summation Of Divisors.
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 K_th 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 ≤ 10¹⁵) And An Integer K (1 ≤ K ≤ 10⁵) 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

Submit solution!

hide comments

< Previous 1 2 Next >

	rayhan50001: 2021-10-07 19:53:32 @srijaygusain sorry for the late reply. there are so many users getting accepted. so I think there is no problem in the test case. please check modular operations & calculations. Last edit: 2021-10-07 20:07:54
	srijaygusain: 2021-07-26 05:52:00 @rayhan50001 Could you please check my submission https://www.spoj.com/status/KPOWERSUM,srijaygusain/# ID=28244322. Everything seems correct but throwing Wrong Answer on Test Case 9 Please check test case 9 also Last edit: 2021-07-27 16:27:01
	[Lakshman]: 2021-06-29 11:04:41 @sankalp_7 Your solution will be running against the cube cluster. You can calculate execution per second. https://www.spoj.com/clusters/ https://ark.intel.com/content/www/us/en/ark/products/88172/intel-xeon-processor-e3-1220-v5-8m-cache-3-00-ghz.html
	sankalp_7: 2021-06-29 05:47:42 Can somebody please tell how many operations can we perform in a second. O(t*sqrt(n)) is giving TLE.
	Scape: 2020-04-06 15:37:21 Fix the sample output and the description. You need to print two new lines after printing the sample output. Something like printf("Case %d: %d\n\n", case_no, ans); <<REPLY FROM SETTER>> no matter how many new line you print. i have checked my solution with 1 to 3 newline after your comment and my all solution got accepted. there are a lot of solver who have already solved the problem they also have only one newline in there code. i have also checked your solution with only one newline and it got accepted . i think in spoj newline does not matter. Last edit: 2020-04-09 18:58:28
	rayhan50001: 2019-10-29 11:50:41 TEST CASE UPDATED. :( if you want to check your code/solution, submit again. :) Last edit: 2019-10-29 12:27:16
	prodipdatta7: 2019-10-19 10:18:28 Week dataset :\| <REPLY> i tried to give as much as hard possible. :( :( <REPLY> i will try to add more test cases.. Last edit: 2019-10-29 11:05:16
	joydas0111: 2018-09-20 18:12:10 getting TLE can anyone give any hint on this problem
	[Lakshman]: 2018-09-16 20:05:15 @problem setter, Even if you set a new problem with new constraints which you have mentioned (Extra_Challenge: N<=10^18, T<=1000 TL: 1s) will not be enough, If you are still interested in setting a challenge make T <=5000 or 10000 <<<REPLY>>>: okay i will try. but i checked with only 1000 didn't check 5000 or 10000. :) thank you. bdw i am not good enough :( . Last edit: 2018-09-20 21:14:04
	julkas: 2018-09-16 13:32:24 @rayhan50001 Where is Extra_Challenge problem with new constraints? <<<REPLY>>>: just try yourself. :) Last edit: 2018-09-20 21:15:07

Submit solution!

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