/*
プログラミングのお題スレ Part12
//mevius.5ch.net/test/read.cgi/tech/1538096947/17
17 名前:デフォルトの名無しさん[] 投稿日:2018/10/01(月) 20:03:33.29 ID:IziOBEHB
お題:f(n)::={nを連続するいくつかの正整数の和として表す表し方の総数}とおく
例えば、15=7+8=4+5+6=1+2+3+4+5よりf(15)=4である
上限Nが与えられたとき、n<=Nでf(n)が奇数となるようなnをすべて足し合わせた値を求めよ
10 -> 24
100 -> 665
1000 -> 18006
10000 -> 571940
100000 -> 18010994
1000000 -> 569929080
10000000 -> 18001029437
100000000 -> 569128815672
1000000000 -> 17994029079715
*/
class Ideone
{
public static void main
(String[] args
) {
solve(10);
solve(100);
solve(1000);
solve(10000);
solve(100000);
solve(1000000);
solve(10000000);
solve(100000000);
solve(1000000000);
}
static void solve(int n)
{
for(int i = 1; i <= n && i > 0; i <<= 1) result.set(i);
int sqrtN
= (int) Math.
sqrt(n
); for (int p = 3; p <= sqrtN; p += 2)
{
if (primeSet.get(p)) continue;
for (int i = p + p; i <= sqrtN; i += p)
primeSet.set(i);
long pp = p * p;
for (int i = 1; i > 0; i = result.nextSetBit(i + 1))
{
if (i * pp > n) break;
result.set((int) (i * pp));
}
}
System.
out.
printf("%d -> %d%n", n, result.
stream().
asLongStream().
sum()); }
}
LyoK44OX44Ot44Kw44Op44Of44Oz44Kw44Gu44GK6aGM44K544OsIFBhcnQxMiAKLy9tZXZpdXMuNWNoLm5ldC90ZXN0L3JlYWQuY2dpL3RlY2gvMTUzODA5Njk0Ny8xNwogCjE3IOWQjeWJje+8muODh+ODleOCqeODq+ODiOOBruWQjeeEoeOBl+OBleOCk1tdIOaKleeov+aXpe+8mjIwMTgvMTAvMDEo5pyIKSAyMDowMzozMy4yOSBJRDpJemlPQkVIQgrjgYrpoYzvvJpmKG4pOjo9e27jgpLpgKPntprjgZnjgovjgYTjgY/jgaTjgYvjga7mraPmlbTmlbDjga7lkozjgajjgZfjgabooajjgZnooajjgZfmlrnjga7nt4/mlbB944Go44GK44GPCuS+i+OBiOOBsOOAgTE1PTcrOD00KzUrNj0xKzIrMys0KzXjgojjgopmKDE1KT0044Gn44GC44KLCuS4iumZkE7jgYzkuI7jgYjjgonjgozjgZ/jgajjgY3jgIFuPD1O44GnZihuKeOBjOWlh+aVsOOBqOOBquOCi+OCiOOBhuOBqm7jgpLjgZnjgbnjgabotrPjgZflkIjjgo/jgZvjgZ/lgKTjgpLmsYLjgoHjgogKIAoxMCAtPiAyNAoxMDAgLT4gNjY1CjEwMDAgLT4gMTgwMDYKMTAwMDAgLT4gNTcxOTQwCjEwMDAwMCAtPiAxODAxMDk5NAoxMDAwMDAwIC0+IDU2OTkyOTA4MAoxMDAwMDAwMCAtPiAxODAwMTAyOTQzNwoxMDAwMDAwMDAgLT4gNTY5MTI4ODE1NjcyCjEwMDAwMDAwMDAgLT4gMTc5OTQwMjkwNzk3MTUKKi8KIApjbGFzcyBJZGVvbmUKewoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpCgl7CgkJc29sdmUoMTApOwogICAgICAgIHNvbHZlKDEwMCk7CiAgICAgICAgc29sdmUoMTAwMCk7CiAgICAgICAgc29sdmUoMTAwMDApOwogICAgICAgIHNvbHZlKDEwMDAwMCk7CiAgICAgICAgc29sdmUoMTAwMDAwMCk7CiAgICAgICAgc29sdmUoMTAwMDAwMDApOwogICAgICAgIHNvbHZlKDEwMDAwMDAwMCk7CiAgICAgICAgc29sdmUoMTAwMDAwMDAwMCk7CiAgICB9CiAKICAgIHN0YXRpYyB2b2lkIHNvbHZlKGludCBuKQogICAgewogICAgICAgIGphdmEudXRpbC5CaXRTZXQgcHJpbWVTZXQgPSBuZXcgamF2YS51dGlsLkJpdFNldCgpOwogICAgICAgIGphdmEudXRpbC5CaXRTZXQgcmVzdWx0ID0gbmV3IGphdmEudXRpbC5CaXRTZXQoKTsKICAgICAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG4gJiYgaSA+IDA7IGkgPDw9IDEpIHJlc3VsdC5zZXQoaSk7CgogICAgICAgIGludCBzcXJ0TiA9IChpbnQpIE1hdGguc3FydChuKTsKICAgICAgICBmb3IgKGludCBwID0gMzsgcCA8PSBzcXJ0TjsgcCArPSAyKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHByaW1lU2V0LmdldChwKSkgY29udGludWU7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSBwICsgcDsgaSA8PSBzcXJ0TjsgaSArPSBwKQogICAgICAgICAgICAgICAgcHJpbWVTZXQuc2V0KGkpOwoKICAgICAgICAgICAgbG9uZyBwcCA9IHAgKiBwOwogICAgICAgICAgICBmb3IgKGludCBpID0gMTsgaSA+IDA7IGkgPSByZXN1bHQubmV4dFNldEJpdChpICsgMSkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChpICogcHAgPiBuKSBicmVhazsKICAgICAgICAgICAgICAgIHJlc3VsdC5zZXQoKGludCkgKGkgKiBwcCkpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCIlZCAtPiAlZCVuIiwgbiwgcmVzdWx0LnN0cmVhbSgpLmFzTG9uZ1N0cmVhbSgpLnN1bSgpKTsKICAgIH0KfQ==