hey guys :D
I have this small math problem,
( a * b ) mod n = 1
Given a, n:
find the smallest value of 'b' that satisfies the equation above.
any Idea about how to find the answer better than linear time search.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:28:42
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:28:42
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 06:06:19 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
this is the same as finding the inverse of A (mod C) right ??
Yes, it's the same. Wikipedia article has some examples.
one more question please, who to choose the proper values for a, n
ikatanic any constraints on values other than 'a' and 'n' should be co primes ??
Nope. Extended Euclidean algorithm is used to solve the equation Ax+By=GCD(A,B) and since GCD(a,n)=1 the equation a*b-k*n=1=GCD(a,n) has infinitely many solutions.
But I found this statement on some website:
"Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)"
this is for the formula above in my post.
You are not right. GCD(a, n) must be equal to 1, otherwise it has no solution. You can read here
He knows that, I just said that there is not another constraint.
(a*b) mod n = 1 means that (a*b) = k*n+1 for some integer k>=0.
a*b-k*n = 1 is an equation of the form Ax+By=C which can be solved using Extended Euclidean algorithm.
Update: When I started writing my comment I didn't see that ikatanic has commented, sorry :)
P_Nyagolov thank you and ikatanic :D