You are not logged in. Please login at www.codechef.com to post your questions!

×

WA in FCUBE. Getting 0.15 points

1
1

Question: http://www.codechef.com/LTIME21/problems/FCUBE

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 :- http://ideone.com/niPoP8

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

asked 22 Feb '15, 14:37

dhruvchandhok's gravatar image

5★dhruvchandhok
413
accept rate: 0%

edited 22 Feb '15, 14:55

1

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

(22 Feb '15, 14:52) abcdexter242★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×550
×7

question asked: 22 Feb '15, 14:37

question was seen: 464 times

last updated: 22 Feb '15, 14:55