### dedicated0809's blog

By dedicated0809, history, 5 weeks ago,

I am dumbfounded whenever i face a problem which requires coming out with a formula on your own! especially when it's related to maths. Like the Your text to link here... 1511B - Длина НОД. I started by reading the problem and re-reading and doing that in a loop and even the slightest hint of the answer did not start materializing inside my head. Tips on tackling that types of questions?..

ps:- i learned about gcd, co-prime etc but still it's literally of no help to me and i like to think that I'm not that bad at general maths either!!

Any tips or tricks for facing those kind of problems headon is appreciated!

• -21

 » 5 weeks ago, # |   0 If you have learned some theory, try to exercise purely math problems from math olympiads
 » 5 weeks ago, # | ← Rev. 2 →   0 Instead of searching immediately for a formula, try to understand how the problem works. Now I'll try to explain a "path" to the solution. For example, you may try to fix $x$ and check the possible values of $y$ and $g = \gcd(x, y)$. This is a bit uncomfortable, it may be better to fix $g$ instead. $x$ and $y$ are multiples of $g$. The only additional condition required is that $\gcd(x / g, y / g) = 1$. At this point, you may find that, if the leading digits of $g$, $x / g$ and $y / g$ are small, $x / g$ should have $a - c + 1$ digits and $y / g$ should have $b - c + 1$ digits. Moreover, $g$ is basically useless, so you can set it to $10^{c-1}$. In this way, you don't have to worry about leading digits of $x / g$ and $y / g$. The new problem is: find $n = x/g$, $m = y/g$ with a fixed number of digits and $\gcd(n, m) = 1$. There are many possible constructions: for example, $n = 11^{a - c}$, $m = 10^{b - c}$.