NeverMa573r's blog

A different approach to 1925B
By NeverMa573r, history, 8 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

        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

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

              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)

              → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply