Блог пользователя skpro19

Автор skpro19, история, 8 лет назад, По-английски

The question is this.

I went through one of the submitted solutions:

I understood that for the solution to exist C must be divisible by g = gcd(A, B);

But, how are we getting the final values for x and y ?

Also, it would be very nice if someone can suggest some nice problems to practice on this topic.

Thanks!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Good day to you!

The solution uses Extended Euclidean Algorithm

To practice this problem more, you can try — for example — this problem.

You can also try any problem, which requires "Modular Inversion", which can be counted by Extended GCD too

Good Luck!