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$$$ $$$->$$$ $$$A + B = a + b$$$
$$$->$$$ $$$sum(a, b) \ doesn't \ change \ after \ T \ operation$$$
$$$Let \ sum = a + b, \ one \ operation \ can \ be \ re-write \ as$$$
$$$if$$$ $$$(a < sum - a)$$$ $$$b = b - a$$$, $$$a = 2a$$$
$$$else$$$ $$$a = a - (sum - a)$$$, $$$b = 2b$$$
$$$if$$$ $$$(2a < sum)$$$ $$$a = 2a$$$
$$$else$$$ $$$a = a - (sum - a) = 2a - sum$$$
$$$assume$$$ $$$(2a - sum \geq sum)$$$ $$$->$$$ $$$a \geq sum = a + b$$$ $$$->$$$ $$$b \leq 0$$$
$$$if$$$ $$$(b < 0)$$$ $$$->$$$ $$$out \ of \ range$$$ $$$->$$$ $$$a = 2a - sum < sum$$$
$$$->$$$ $$$A = (a * 2 ^ t)$$$ % $$$sum$$$, $$$B = sum - A$$$
$$$if$$$ $$$(b = 0)$$$ $$$->$$$ $$$output \ initial \ a \ and \ b$$$