Hello, everyone!
I’d like to share a problem I came up with, which I believe to be quite unique (as I haven’t come across anything similar elsewhere).
I’ve created many problems for various platforms, but Timosh and Number Theory is the one I consider the most original. I hope you find it intriguing!
The problem is quite challenging — only 5 participants managed to solve it under contest conditions. If you’re looking for an even tougher challenge, there’s a harder version available: Timosh and Number Theory #2.
I’d love to hear your thoughts on this problem!
I want to say Timosh is great ! orz
Timosh orz
Any hints for hard version?
Sure
What can be the size of the desired range $$$[L, R]$$$? (the value of $$$R-L+1$$$)
Let $$$S = R-L+1$$$.
then for the constraints of $$$a$$$ and $$$x$$$, $$$S$$$ should be a number in some range($$$l <= S <= r$$$ for some $$$l$$$ and $$$r$$$, which are related to $$$a$$$ and $$$x$$$ somehow). Same goes for the constraints of $$$b$$$ and $$$y$$$. What is the relation here?
Let's say we chose some $$$S$$$, which is found to be valid. Also, let's say we found a range $$$[L_1, R_1]$$$, where $$$x$$$ integers are divisible by $$$a$$$. Then, any range of form $$$[L_1+a\cdot n, R_1 + a \cdot n]$$$ has the same property for any integer $$$n$$$. The same goes for $$$b$$$, $$$[L_2 + b \cdot k, R_2 + b \cdot k]$$$. The only thin left to do, is match the ranges, i.e. $$$L_1 + a \cdot n = L_2 + b \cdot k$$$ for some $$$n$$$ and $$$k$$$. How to solve this equation?
Diophantine equation.
in the easy version we dont have to solve the diophantine equation ?
No, you don't have to
whats the intended way for easy version then ?