Problem 464 のバックアップの現在との差分(No.0)

• バックアップ一覧
• 差分 を表示
• ソース を表示
• バックアップ を表示
• Problem 464 へ行く。

• 追加された行はこの色です。
• 削除された行はこの色です。

*[[Problem 464:http://projecteuler.net/problem=464]] 「メビウス関数と区間」 [#ob8df9eb]

''メビウス関数''は '''μ'''('''n''') で表され, 次のように定義される:

- '''μ'''('''n''') = (-1)&sup{'''ω'''('''n''')};, '''n''' が無平方の場合 (ここで '''ω'''('''n''') は '''n''' の相異なる素因数の数)
- '''μ'''('''n''') = 0, '''n''' が無平方でない場合

区間 ['''a''','''b'''] 内で '''μ'''('''n''') = 1 となるような整数 '''n''' の個数を P('''a''','''b''') としよう.~
区間 ['''a''','''b'''] 内で '''μ'''('''n''') = -1 となるような整数 '''n''' の個数を N('''a''','''b''') としよう.~
例えば, P(2,10) = 2, N(2,10) = 4.

以下のような整数の組 ('''a''','''b''') の個数を C('''n''') としよう:

- 1 ≤ '''a''' ≤ '''b''' ≤ '''n'''
- 99·N('''a''','''b''') ≤ 100·P('''a''','''b''')
- 99·P('''a''','''b''') ≤ 100·N('''a''','''b''')

例として, C(10) = 13, C(500) = 16676, そして C(10 000) = 20155319.

C(20 000 000) を求めよ.