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
hide comments
|
nati__22:
2021-06-16 12:26:08
AC in one go ... 10 points |
|
dewa251202:
2018-10-02 10:15:26
O(len(y)^2) only got 2 pts |
|
alanturing13:
2017-03-30 18:31:51
python's pow method seems to work
|
|
shubh809:
2016-10-19 15:01:04
10 points after some efforts |
|
Abhishek:
2016-09-17 13:41:41
Pythons default mod pow beats the question, so implementing fast modular exponentiation should do it |
|
Md. Istiyak ahmed:
2013-12-11 17:40:56
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 |
|
Micha³ Ma³afiejski:
2009-12-16 07:19:55
2<=x,n<=2^30, 0 <= y <= 2^30 - easy
|
|
Paulo Roberto Santos de Sousa:
2009-03-12 09:33:57
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 |
|
[Trichromatic] XilinX:
2009-03-12 08:39:25
Maybe - My program (in both C and Python) can haddle test case like that. |
|
|
Paulo Roberto Santos de Sousa:
2009-03-12 07:52:13
For easy tests 2<=x,n<=2^30 e 0<=y<=2^30.
|
| Added by: | mima |
| Date: | 2006-02-27 |
| Time limit: | 1s-8.932s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS