11752 - The Super Powers

[Angeh]

Any Ideas How To solve This Problem efficiently ....
and How To handle The overflow?
any help is appreciated.....

[arifcsecu]

How can i solve this ?
I have got TLE.

Please help any body.

[arifcsecu]

mdepiym
Admin
moseley198byas
qfrab6fk
jiying2034

// What is this ..................
It is very important forum for the programmers but not for others ...............

[Jehad Uddin]

Take the composite powers of nos upto 2^16
2^4
2^6
...
3^4
3^6
..
4^4
4^6
..
To handle overflow before multiplying just chek it log(no1)+log(no2)<64log(2)

[plamplam]

My best for this problem is 0.032 (The best for this problem is 0.028 ). And I didn't even optimize my code, no I/O opt nothing. (May be someday I can beat the best record with I/O Optimization ). I am not going to tell you my algorithm....no way guys but I can give you hints. You have to print a total of 67385 lines(including 1). And think a bit, what property would a number have if it is the power of at least two different positive integers? For example 16 = 2^4 and 4^2 and 729 = 3^6 and 9^3 and 27^2 etc. No more hints for you, you must solve this problem by yourself Be assured, you won't get WA or TLE if your algo is correct and efficient and you are printing exactly 67385 lines(In increasing order). (You can check this by increasing a counter variable starting from 0 whenever you are printing a line and later just print that counter variable )
Last hint(probably the most useful one) : You have to print all the numbers in ascending order as specified in the description. However this does not necessarily mean that you have to FIND all such numbers in ascending order.

[plamplam]

And @Angeh the best way to handle overflow in this problem is by using log/ln (any one will do), but I didn't use the log/ln function in my program

[outsbook]

For check Overflow
You can use

Code: Select all

int bit = 64;
int power= ceil(bit  / (log(powerBase)/log(2)));

Example:
1. If powerBase=3 then power=41 (i.e. the maximum power of 3 is 40, 3^40 < 2^64-1(unsigned long long range)). 3^41 is overflow at 64 bit integer.

2. If powerBase=5 then power=28 (i.e. the maximum power of 5 is 27, 5^27 < 2^64-1(unsigned long long range)). 5^28 is overflow at 64 bit integer.