Обсуждение @ 1204. Идемпотенты @ Timus Online Judge

Stefan Ciobaca Can someone explain this problem to me? [2] // Задача 1204. Идемпотенты 22 мар 2002 03:41

I can have my program solve it in sqrt(n) but this is not good enough.
Please tell me how to optimize. 10x in advance

MadPsyentist/Sam Re: Can someone explain this problem to me? [1] // Задача 1204. Идемпотенты 22 мар 2002 18:04

As I guess, your O(sqrt(n)) time is from finding ap+bq=1 , right?
If so , you can use extended Euclidean algorithm (one which find GCD)
to solve this equation.

Dragon Re: Can someone explain this problem to me? // Задача 1204. Идемпотенты 19 окт 2002 15:20

Right! I got AC! (the GCD of p and q is 1!!!!!!!)

Обсуждение задачи 1204. Идемпотенты