After looking at the hints for 1925B (https://mirror.codeforces.com/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?
easy problem just look for the smallest divisor of x that is greater than or equal to n , answer is x by that number
how did you arrive to that solution? Did you just know the gcd property?
you are acting like the only one who knows euclids's lemma it is very famous upd: my sol above gives WA
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
actually i just guessed the answer and did not use the property upd:finally AC
ah, so its just intuitive to you. But I assume you knew euclids lemma before this?
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)
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.
Thanks so much! This makes a lot of sense