### 11490 - Just Another Problem

Posted:

**Mon Sep 15, 2008 1:21 am**My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.

TIA

Vinay Emani

TIA

Vinay Emani

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=42&t=42310

Page **1** of **1**

Posted: **Mon Sep 15, 2008 1:21 am**

My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.

TIA

Vinay Emani

TIA

Vinay Emani

Posted: **Tue Sep 16, 2008 4:22 am**

Hi Robert,

How did you solve it in 10ms . Is it possible to construct the solutions

directly without searching? Thanks!

How did you solve it in 10ms . Is it possible to construct the solutions

directly without searching? Thanks!

Posted: **Tue Sep 16, 2008 2:56 pm**

can anyone give me some hint how to solve the problem quickly

Posted: **Tue Sep 16, 2008 10:09 pm**

The problem is equivalent to factorize n (it is a little algebra to figure out the factors) for this I've used Pollard rho method (by Brent's modification).baodog wrote:Hi Robert,

How did you solve it in 10ms . Is it possible to construct the solutions

directly without searching? Thanks!

Posted: **Thu Jul 02, 2009 4:56 pm**

My O(sqrt(S)) algorithm got AC in 1.3sNaani wrote:My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.

TIA

Vinay Emani