Hello, I'm Capricornian. I have a problem, which seems to be easy, but I have no idea how to achieve a solution of that problem in approriate time limit.
Can you help me to figure it out and find how it works?
This is the problem statement:
Number Distribution
Giving two integers A and B (A and B is in range [0..2E9]) and a non-negative integer T < 1E18.
In one operation, this rule is followed :
if (A < B) B = B - A, A = 2 * A, ;
else A = A - B, B = 2 * B;
Calculate A and B after T operations. (I have figured out that if you do these sequences of operation enough times, you will get back A and B in the beginning case, but I can't find the rule behind that).
Thanks for helping !
Capricornian.
$$$Let \ A, \ B \ be \ new \ a, \ b \ after \ an \ operation$$$
$$$B = b - a$$$, $$$A = 2a$$$ $$$- \gt $$$ $$$A + B = a + b$$$
$$$- \gt $$$ $$$sum(a, b) \ doesn't \ change \ after \ T \ operation$$$
$$$Let \ sum = a + b, \ one \ operation \ can \ be \ re-write \ as$$$
$$$if$$$ $$$(a \lt sum - a)$$$ $$$b = b - a$$$, $$$a = 2a$$$
$$$else$$$ $$$a = a - (sum - a)$$$, $$$b = 2b$$$
$$$if$$$ $$$(2a \lt sum)$$$ $$$a = 2a$$$
$$$else$$$ $$$a = a - (sum - a) = 2a - sum$$$
$$$assume$$$ $$$(2a - sum \geq sum)$$$ $$$- \gt $$$ $$$a \geq sum = a + b$$$ $$$- \gt $$$ $$$b \leq 0$$$
$$$if$$$ $$$(b \lt 0)$$$ $$$- \gt $$$ $$$out \ of \ range$$$ $$$- \gt $$$ $$$a = 2a - sum \lt sum$$$
$$$- \gt $$$ $$$A = (a * 2 ^ t)$$$ % $$$sum$$$, $$$B = sum - A$$$
$$$if$$$ $$$(b = 0)$$$ $$$- \gt $$$ $$$output \ initial \ a \ and \ b$$$