WA in FCUBE. Getting 0.15 points

general
,
1

Question: CodeChef: Practical coding for everyone

My logic->
I inserted all numbers in a[].

I had all primes uptil 10^6. First of all I removed all prime factors from all the number( in a[] ) and maintained their count in b[] array. Now a[] is the residual array .

Then factoring all numbers will cause TLE as a[i] can go upto 10^18. But I don’t need to do it.

I just to consider a factor individually only if it appears more than one time.

This can happen only in 2 cases ,

1)if any of two elements in the residual array have a gcd > 1, the gcd is another factor that I need to consider.
2)if any element in the residual array>1 and is a perfect square.

If still any element in the residual array is still greater than one, I just need to cube that and multiply in my answer( even if the number is not prime ).

My Code :- niPoP8 - Online C++0x Compiler & Debugging Tool - Ideone.com

Can someone help me find whether the flaw is in the logic or the code?

1 Like
2

Good logic, I was just using that sieve in root N and then adding to multiset STL. But it was even TLE in 10^9. Couldn’t do much, exams hain ;-D

1 Like