dedicated0809's blog

By dedicated0809, history, 5 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • -21
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If you have learned some theory, try to exercise purely math problems from math olympiads

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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}$$$.