ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1854. Negotiations with Parthians

How do you solve this problem ?
Posted by rohit 25 Sep 2011 01:12
Some hints please. My algo takes too much time.
Re: How do you solve this problem ?
Posted by Pavel Kovalenko 27 Sep 2011 16:44
You need factoring N by numbers 2..10^6. If after factoring N>1 and N not prime, then your N=p*q, where p and q - prime numbers.

Edited by author 27.09.2011 16:46
Re: How do you solve this problem ?
Posted by svr 10 Oct 2011 14:33
most difficult case n=p*p, where p- is prime
for it case quick  _int64 sqrt(__int64 n) function is needed,
in other cases there is a factor of n which is <1000000.
Re: How do you solve this problem ?
Posted by arrammis 19 Jan 2015 01:03
svr what should be the output when n = p*p where p is prime ??

i guess just n ? becuase n is already odd and its the maximum ?

Edited by author 19.01.2015 01:04
Re: How do you solve this problem ?
Posted by die_young 8 Jul 2018 18:21
I just did straight forward factorization (with rho) of an input number and then divided it by primes that have an odd power in factorization.

0.31 ms, 1400 kb.

Edited by author 08.07.2018 18:21
Re: How do you solve this problem ?
Posted by Hristo Nikolaev (B&W) 25 Dec 2022 23:22
AC in 0.015 (in plain C) with something much simpler than RHO.

- start factorizing the simplest way they teach you in the kindergarten
- when the test reach large values, check if the reminder has a perfect square
-- if so - return the square and count as it is a prime divisor ^2
(because even if it can be factorized, it will be an amount of multipliers ^2)
-- if no - stop checking
(because the reminders are obviously large prime values ^1 and can be ignored)
- multiply all primes with even powers * primers with odd powers (n) >= 3 with power n-1

I bet it can be accepted in 0.001 if Intel C 7 was still a compiler option.