Problem 433
の編集
http://odz.sakura.ne.jp/projecteuler/index.php?Problem+433
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 433:http://projecteuler.net/problem=433]] 「ユークリッドの互除法のステップ数」 [#n6482551] '''x'''&sub{0}; と '''y'''&sub{0}; の最大公約数を''ユークリッドの互除法'' (Euclid's algorithm) を用いて割り出す時に必要となるステップ数を E('''x'''&sub{0};, '''y'''&sub{0};) としよう. より形式的に表すと:~ '''x'''&sub{1}; = '''y'''&sub{0};, '''y'''&sub{1}; = '''x'''&sub{0}; mod '''y'''&sub{0};~ '''x'''&sub{'''n'''}; = '''y'''&sub{'''n'''-1};, '''y'''&sub{'''n'''}; = '''x'''&sub{'''n'''-1}; mod '''y'''&sub{'''n'''-1};~ E('''x'''&sub{0};, '''y'''&sub{0};) は '''y'''&sub{'''n'''}; = 0 となるような最小の '''n''' である. E(1,1) = 1, E(10,6) = 3, そして E(6,10) = 4 であることがわかっている. 1 ≤ '''x''','''y''' ≤ N における E('''x''', '''y''') の和を S(N) と定義しよう.~ S(1) = 1, S(10) = 221, そして S(100) = 39826 であることがわかっている. S(5·10&sup{6};) を求めよ.
タイムスタンプを変更しない
*[[Problem 433:http://projecteuler.net/problem=433]] 「ユークリッドの互除法のステップ数」 [#n6482551] '''x'''&sub{0}; と '''y'''&sub{0}; の最大公約数を''ユークリッドの互除法'' (Euclid's algorithm) を用いて割り出す時に必要となるステップ数を E('''x'''&sub{0};, '''y'''&sub{0};) としよう. より形式的に表すと:~ '''x'''&sub{1}; = '''y'''&sub{0};, '''y'''&sub{1}; = '''x'''&sub{0}; mod '''y'''&sub{0};~ '''x'''&sub{'''n'''}; = '''y'''&sub{'''n'''-1};, '''y'''&sub{'''n'''}; = '''x'''&sub{'''n'''-1}; mod '''y'''&sub{'''n'''-1};~ E('''x'''&sub{0};, '''y'''&sub{0};) は '''y'''&sub{'''n'''}; = 0 となるような最小の '''n''' である. E(1,1) = 1, E(10,6) = 3, そして E(6,10) = 4 であることがわかっている. 1 ≤ '''x''','''y''' ≤ N における E('''x''', '''y''') の和を S(N) と定義しよう.~ S(1) = 1, S(10) = 221, そして S(100) = 39826 であることがわかっている. S(5·10&sup{6};) を求めよ.
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
