Capricornian's blog

By Capricornian, history, 5 years ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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