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

A different approach to 1925B
Автор NeverMa573r, история, 8 месяцев назад, По-английски

After looking at the hints for 1925B (https://codeforces.net/problemset/problem/1925/B), I realized the solution by knowing the properties of gcd(a,b) = gcd(a, a + b). But since this is codeforces, I'm wondering how I would have got to the solution if I hadn't known this property about gcd. For those who have solved this without using mathematical properties, how did you solve this?

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

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

easy problem just look for the smallest divisor of x that is greater than or equal to n , answer is x by that number

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

    how did you arrive to that solution? Did you just know the gcd property?

    → Ответить
    • »
      »
      »
      8 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      you are acting like the only one who knows euclids's lemma it is very famous upd: my sol above gives WA

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

        ok, so you just knew the property. I'm looking for someones thought process if they didn't know it. I assume in the future, there will be problems featuring mathematical properties that not everyone knows, and I assume that there should be a way to get to the solution without knowing the properties

        → Ответить
        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          actually i just guessed the answer and did not use the property upd:finally AC

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

            ah, so its just intuitive to you. But I assume you knew euclids lemma before this?

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

              yeah i just read samples and it hit into my head i usually apply this for B's which have just very little input and are usually based on formula or any answer that is at most O(log n)

              → Ответить
»
8 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Let y be the maximum gcd of all subproblems difficulties so y*a1 + y*a2 +...+y*an = x Then y(a1 +...+an) = x Then a1+ ... + an is a divisor of x, and to make y big, we should make that sum as small as possible, so we can make a1+...+ a(n-1) = n-1 and we will choose an such that the sum is a divisor of x.

→ Ответить