作者LPH66 (f0VMRgEBA)
看板puzzle
标题[中译] ProjectEuler 433 Steps in Euclid's algorithm
时间Tue Jun 25 00:19:43 2013
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
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.118.113.29