k790alex's blog

[Question] Extended Euclidean Algorithm applications
By k790alex, 10 years ago, In English

Hi, I read this Topic and I was thinking about its applications in contest but I couldn't get any.

I only know that this algorithm is useful for cryptography but I worder how it could be used in contests.

If you could provide me an example I would be grateful and a problem would be useful too.

Thanks in advance.

UPDATE: thanks to all, i continue reading and I found this link, it is another application.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For example that or that. Both of them are quite common sub-tasks.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Here are some problems on UVA online judge from uHunt

10104 — Euclid Problem

10090 — Marbles

10633 — Rare Easy Problem

10673 — Play with Floor and Ceil

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems, like the third problem can be solved using simple math.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try to solve Chinese remainder problem using extended Euclidean algorithm.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain anymore?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Does the explanation hzyfr did make sence or you need more clarification?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I need more information. :) Thank you.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Try to consider the problem of finding A mod N = n1*n2*...*nk given m1 = A mod n1, m2 = A mod n2, ..., mk = A mod nk.

          You can do that via finding A mod n1*n2, A mod n1*n2*n3, A mod n1*n2*n3*n4, ..., A mod N.

          It is sufficient to consider the case of two variables.

          A = k1*n1 + m1 = k2*n2 + m2

          k1*n1 — k2*n2 = m2 — m1

          We can find k1 and k2 using Extended GCD.

          You can find comprehensive article on CRT on wikipedia.

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Extend-gcd will give you one solution to the equation ax+by=gcd(x,y). That is a very basic thing when you are trying to deal with linear modular equations and something related to that.

Chinese Remainder Theorem is also a useful tool in solving modular problems as NotImplemented mentioned. You can combine extend-gcd algorithm with CRT to get the result.

→ Reply