給你 (A, B) ,只有一種操作 -> (A-B, B+B) (A>B時),問你 幾次 操作後會變成 (0, C)。

由於你的操作只有涉及 + -,所以可以先把 g=GCD(A, B) 提出來,變成 (A, B)=(A/g, B/g)。

手動模擬一下,發現只有當 (A'+B') = 2^k 時才有解,而 k 就是次數。

我的code

http://snipt.org/zfiz0

p.s: 詳細證明可以參考這篇 http://d.ream.at/wp-content/attachments/sgu126.pdf

 

 

 

創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()