| Submit | All submissions | Best solutions | Back to list |
MPOWER - Power it! |
| Wersja polska | English version |
Dla danych liczb x, y oraz n wyznacz
czyli liczbę r taką, że 0 <= r < n oraz n | (xy - r).
Wejście
t [liczba przypadków testowych <= 10]
x y n [2 <= x, n <= 230, 0 <= y <= 230 - łatwe (1010000 - trudne)
Pierwsze dwa testy są łatwe, kolejne cztery są trudne. Limit punktów (zadanie zostaje zaakceptowane) wynosi 2 pkt.
Wyjście
r [takie, że xy = r (mod n)]
Przykład 1 (łatwy)
Wejście: 2 54015779 489100829 472960975 827371214 966345673 443599139 Wyjście: 350431544 391669493
Przykład 2 (trudny)
Wejście: 1 29809803 47901912849872523461864631327232122 1008098565 Wyjście: 718185534
| Added by: | mima |
| Date: | 2006-02-27 |
| Time limit: | 1s-8.932s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
2021-06-16 12:26:08
AC in one go ... 10 points |
|
|
2018-10-02 10:15:26
O(len(y)^2) only got 2 pts |
|
|
2017-03-30 18:31:51
python's pow method seems to work can anyone explain how it is implemented |
|
|
2016-10-19 15:01:04
10 points after some efforts |
|
|
2016-09-17 13:41:41 Abhishek
Pythons default mod pow beats the question, so implementing fast modular exponentiation should do it |
|
|
2013-12-11 17:40:56 Md. Istiyak ahmed
I solved the easy one with bigmod which is log(n) . But for harder how can I handle the large value of y ? Last edit: 2013-12-11 17:45:44 |
|
|
2009-12-16 07:19:55 Micha³ Ma³afiejski
2<=x,n<=2^30, 0 <= y <= 2^30 - easy 2<=x,n<=2^30, 0 <= y <= 10^10000 - hard |
|
|
2009-03-12 09:33:57 Paulo Roberto Santos de Sousa
Thanks! I think that the best algorithm for solve that problem is the fast modular exponentiation, but my code get just TLE. Someone can help me? Last edit: 2009-03-12 09:33:57 |
|
|
2009-03-12 08:39:25 [Trichromatic] XilinX
Maybe - My program (in both C and Python) can haddle test case like that. |
|
|
2009-03-12 07:52:13 Paulo Roberto Santos de Sousa
For easy tests 2<=x,n<=2^30 e 0<=y<=2^30. For hard tests 2<=x,n<=10^10000 e 0<=y<=10^10000? |
RSS