SPOJ.com - Problem INTEGER1

INTEGER1 - Power of Integer

#binary-search

For a given positive integer y (y > 1), if we can find a largest integer k and a smallest positive integer x, such that x^k=y, then the power of y is regarded as k.

Calculate the sum of the power of the integers from a to b. (2<= a <= b <=10¹⁸)

Input

The input consists of multiple test cases.

For each test case, there is one line containing two integers a and b.

End of input is indicated by a line containing two zeros.

Output

For each test case, output the sum of the power of the integers from a to b.

Example

Input:
2 10
248832 248832
0 0

Output:
13
5

Submit solution!

hide comments



	DK...: 2019-12-23 02:17:30 Im done with this problem, i tried several ways to solve it, but all of them got WA. Even I used python to avoid overflows, but in the end all my solutions got WA.
	eagle93: 2018-07-09 14:09:13 I don't know why this happened, but the same code gets AC with C++ 4.3.2, but WA with CPP14, really strange!!
	holmesherlock: 2017-02-08 18:45:03 giving me WA over and over..dont know where it is wrong,,tested over different test cases from toolkit,,passed all but still,,,,,,, my ans for 2 , 1000000000000000000 is 1000000001002087980,,someone plz hlp.. Last edit: 2017-02-08 18:49:57
	Naman Goyal: 2014-07-16 08:32:06 Great problem. You can use long double calculation for finding nth root for initial guess and then correct it with INT 64 verification. For INT 64 verification take care of overflows.
	wisfaq: 2013-05-24 12:04:09 Totally ununderstandable why such a nice and doable problem has so few accepted solutions. Last edit: 2013-05-24 18:48:55
	Harshit Agrawal: 2012-09-10 09:14:38 I am getting WA but could not find any test case for that. what is the answer for a=2 and b=1000000000000000000 ? My answer is 1000000001002087980. Please help !
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-09-02 11:19:07 use double --> TLE use int --> WA use long long --> AC Nice problem :-)
	cprocoder: 2011-07-13 11:52:18 Really very nice problem
	sandeep pandey: 2011-04-09 19:33:39 Really nice problem. Thanks XilinX for adding such a thriling task. Last edit: 2013-11-21 18:20:44
	P != NP: 2010-03-30 18:07:02 don't use doubles or long doubles for this question....it will give WA. Use only long long int. Last edit: 2010-03-30 18:07:44

Submit solution!

Added by:	Fudan University Problem Setters
Date:	2009-05-23
Time limit:	2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:	Fudan University Local Contest #1