Обсуждение @ 1132. Квадратный корень @ Timus Online Judge

Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Послано Huang Yizheng 9 ноя 2001 16:17

Re: Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Послано Algorist 10 ноя 2001 10:18

I think that there is a simple formula that is going to
work....

Does there any mathymatical formula exit?Or I have to improve my enumerating algorithm?

Послано Huang Yizheng 12 ноя 2001 05:03

> I think that there is a simple formula that is going to
> work....

Re: Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Послано XiangGuangTe 9 май 2004 14:45

I know the answer when (n mod 4)=3

The answer is +a^((n+1)/4), -a^((n+1)/4)

But I don't know the answer when (n mod 4)=1

Re: Why I always got time exceeded?How to improve my program?I want to know the best algorithm.

Послано Gheorghe Stefan 10 май 2004 16:12

an efficient algorithm for this problem requires knowing very much of number theory: Legendre Symbols and other (i've found them on the web). You could search the web for quadratic residues modulo n...
if not found, I cand send you "my" source...

Обсуждение задачи 1132. Квадратный корень