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

Автор k790alex, 11 лет назад, По-английски

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.

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

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

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Try to solve Chinese remainder problem using extended Euclidean algorithm.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you explain anymore?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          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.

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

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.