Capricornian's blog

By Capricornian, history, 3 months ago, ,

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.

• +11

 » 3 months ago, # |   0 Auto comment: topic has been updated by Capricornian (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   +17 $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$