*[[Problem 508:https://projecteuler.net/problem=508]] 「i-1進数の整数」 [#f0e09d5d]

ガウス整数 i-1 について考えよう. ガウス整数 '''a'''+'''b'''i の''i-1進数表現''とは, 以下のような数字列 '''d'''&sub{n-1};'''d'''&sub{n-2};...'''d'''&sub{1};'''d'''&sub{0}; からなる有限数列である:

- '''a'''+'''b'''i = '''d'''&sub{'''n'''-1};(i-1)&sup{'''n'''-1}; + '''d'''&sub{'''n'''-2};(i-1)&sup{'''n'''-2}; + ... + '''d'''&sub{1};(i-1) + '''d'''&sub{0};
- それぞれの '''d'''&sub{'''k'''}; は {0,1} のいずれか
- 先行ゼロは持たない, すなわち '''d'''&sub{'''n'''-1}; ≠ 0, ただし '''a'''+'''b'''i が 0 の場合を除く

ガウス整数のi-1進数表現は以下のようになる:

11+24i → 111010110001101~
24-11i → 110010110011~
8+0i → 111000000~
−5+0i → 11001101~
0+0i → 0

意外なことに, 全てのガウス整数は一意のi-1進数表現を持っている.~

'''a'''+'''b'''i の一意なi-1進数表現内の 1 の個数を '''f'''('''a'''+'''b'''i) としよう. 例えば '''f'''(11+24i) = 9, '''f'''(24-11i) = 7.

|'''a'''| ≤ '''L''', そして |'''b'''| ≤ '''L''' となるような全ての整数 '''a''', '''b''' に対する '''f'''('''a'''+'''b'''i) の和を '''B'''('''L''') としよう. 例えば, '''B'''(500) = 10795060.

'''B'''(10&sup{15};) mod 1 000 000 007 を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS