[中译] ProjectEuler 508 Integers in base i-1

楼主: tml (流刑人形)   2015-03-24 04:26:09
508. Integers in base i-1
https://projecteuler.net/problem=508
一个高斯整数a+bi的i-1进位表达式可写成一有限数列d_(n-1)d_(n-2)...d_1d_0满足:
 ‧a+bi = d_(n-1) (i-1)^(n-1) + d_(n-2) (i-1)^(n-2) + ... + d_1 (i-1) + d_0
 ‧每个d_k都是0或1。
 ‧首位不为0,即d_(n-1)≠0,除非a+bi = 0。
下面为一些高斯整数的i-1进位表达式:
11+24i → 111010110001101
24-11i → 110010110011
8+0i → 111000000
-5+0i → 11001101
0+0i → 0
值得一提的是,每个高斯整数都恰有一个i-1进位表达式!
定义f(a+bi)为a+bi的i-1进位表达式中1的总数。
例如,f(11+24i) = 9以及f(24-11i) = 7。
令B(L)为对所有符合|a|≦L以及|b|≦L的整数a和b,f(a+bi)的总和。
例如,B(500) = 10795060。
请求出B(10^15) mod 1000000007。

Links booklink

Contact Us: admin [ a t ] ucptt.com