|
|
問題
十進数の整数nに対し、1からnの整数を二進数で表したときの各々の1の個数の和をF(n)と定義します。
例えば、F(3)=4です。
十進数の1,2,3をそれぞれ二進数で表すと、1,10,11で、1が全部で4回現れるからです。
同様に、F(13)=25となることが確かめられます。
F(10^3)の値を（十進数で）求めて下さい。
F(10^10)の値を（十進数で）求めて下さい。
考察
n=13のとき、
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
0ビット目について、
0,1の繰り返しなので、Q=[(n+1)/2^0]として、
[Q/2]×2^0 と ( Qが奇数のときmod(n+1,2^0)=0、偶数のとき0 )
1ビット目について、
0,0,1,1の繰り返しなので、Q=[(n+1)/2^1]として、
[Q/2]×2^1 と ( Qが奇数のときmod(n+1,2^1)、偶数のとき0 )
2ビット目について、
0,0,0,0,1,1,1,1の繰り返しなので、Q=[(n+1)/2^2]として、
[Q/2]×2^2 と ( Qが奇数のときmod(n+1,2^2)、偶数のとき0 )
3ビット目について、
0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1の繰り返しなので、Q=[(n+1)/2^3]として、
[Q/2]×2^3 と ( Qが奇数のときmod(n+1,2^3)、偶数のとき0 )
（終り）
LET N=13 !10^3 !F(n)
LET S=0 !1の個数
LET B=2^0 !kビット
DO WHILE B<=N
LET Q=INT((N+1)/B) !2^k個ずつの0と1
LET S=S+INT(Q/2)*B
IF MOD(Q,2)=1 THEN LET S=S+MOD(N+1,B)
LET B=B*2 !次へ
LOOP
PRINT S
END
|
|