ProjectEuler 433 Steps in Euclid's algorithm - 拼圖

433. Steps in Euclid's algorithm

http://projecteuler.net/problem=433

令 E(x_0, y_0) 表示求 x_0 與 y_0 的最大公因數時使用歐幾里得算法的步驟數。

形式上來說：
x_1 = y_0, y_1 = x_0 mod y_0
x_n = y_{n-1}, y_n = x_{n-1} mod y_{n-1}
E(x_0, y_0) 即是滿足 y_n = 0 的最小的 n 。

例如 E(1,1) = 1, E(10,6) = 3 及 E(6,10) = 4。

定義 S(N) 為所有 E(x,y) 的和，其中 1 ≦ x,y ≦ N。

給定 S(1) = 1, S(10) = 221 及 S(100) = 39826。

求 S(5*10^6)。

--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308

--