/*
プログラミングのお題スレ 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 final int MAX = Integer.MAX_VALUE;
    static final int[] factor;
    static
    {
        int[] temp = new int[(int) Math.sqrt(MAX)];
        temp[0] = 2;
        int n = 1;
        loop: for (int i = 3, j = (int) Math.sqrt(MAX); i <= j; i += 2) {
            for (int k = 3, l = (int) Math.sqrt(i); k <= l; k += 2) {
                if (i % k == 0) continue loop;
            }
            temp[n++] = i * i;
        }
        factor = java.util.Arrays.copyOf(temp, n);
    }
    
    static void solve(int n)
    {
        if (n < 1) throw new IllegalArgumentException();
        System.out.printf("%d -> %d%n", n, r(n, 1, 0));
    }

    private static long r(int n, long cur, int f)
    {
        long ret = cur;
        for (int i = f; i < factor.length && cur * factor[i] <= n; i++) {
            ret += r(n, cur * factor[i], i);
        }
        return ret;
    }
}

LyoK44OX44Ot44Kw44Op44Of44Oz44Kw44Gu44GK6aGM44K544OsIFBhcnQxMiAKLy9tZXZpdXMuNWNoLm5ldC90ZXN0L3JlYWQuY2dpL3RlY2gvMTUzODA5Njk0Ny8xNwogCjE3IOWQjeWJje+8muODh+ODleOCqeODq+ODiOOBruWQjeeEoeOBl+OBleOCk1tdIOaKleeov+aXpe+8mjIwMTgvMTAvMDEo5pyIKSAyMDowMzozMy4yOSBJRDpJemlPQkVIQgrjgYrpoYzvvJpmKG4pOjo9e27jgpLpgKPntprjgZnjgovjgYTjgY/jgaTjgYvjga7mraPmlbTmlbDjga7lkozjgajjgZfjgabooajjgZnooajjgZfmlrnjga7nt4/mlbB944Go44GK44GPCuS+i+OBiOOBsOOAgTE1PTcrOD00KzUrNj0xKzIrMys0KzXjgojjgopmKDE1KT0044Gn44GC44KLCuS4iumZkE7jgYzkuI7jgYjjgonjgozjgZ/jgajjgY3jgIFuPD1O44GnZihuKeOBjOWlh+aVsOOBqOOBquOCi+OCiOOBhuOBqm7jgpLjgZnjgbnjgabotrPjgZflkIjjgo/jgZvjgZ/lgKTjgpLmsYLjgoHjgogKIAoxMCAtPiAyNAoxMDAgLT4gNjY1CjEwMDAgLT4gMTgwMDYKMTAwMDAgLT4gNTcxOTQwCjEwMDAwMCAtPiAxODAxMDk5NAoxMDAwMDAwIC0+IDU2OTkyOTA4MAoxMDAwMDAwMCAtPiAxODAwMTAyOTQzNwoxMDAwMDAwMDAgLT4gNTY5MTI4ODE1NjcyCjEwMDAwMDAwMDAgLT4gMTc5OTQwMjkwNzk3MTUKKi8KIApjbGFzcyBJZGVvbmUKewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykKICAgIHsKICAgICAgICBzb2x2ZSgxMCk7CiAgICAgICAgc29sdmUoMTAwKTsKICAgICAgICBzb2x2ZSgxMDAwKTsKICAgICAgICBzb2x2ZSgxMDAwMCk7CiAgICAgICAgc29sdmUoMTAwMDAwKTsKICAgICAgICBzb2x2ZSgxMDAwMDAwKTsKICAgICAgICBzb2x2ZSgxMDAwMDAwMCk7CiAgICAgICAgc29sdmUoMTAwMDAwMDAwKTsKICAgICAgICBzb2x2ZSgxMDAwMDAwMDAwKTsKICAgIH0KICAgIAogICAgCiAgICBzdGF0aWMgZmluYWwgaW50IE1BWCA9IEludGVnZXIuTUFYX1ZBTFVFOwogICAgc3RhdGljIGZpbmFsIGludFtdIGZhY3RvcjsKICAgIHN0YXRpYwogICAgewogICAgICAgIGludFtdIHRlbXAgPSBuZXcgaW50WyhpbnQpIE1hdGguc3FydChNQVgpXTsKICAgICAgICB0ZW1wWzBdID0gMjsKICAgICAgICBpbnQgbiA9IDE7CiAgICAgICAgbG9vcDogZm9yIChpbnQgaSA9IDMsIGogPSAoaW50KSBNYXRoLnNxcnQoTUFYKTsgaSA8PSBqOyBpICs9IDIpIHsKICAgICAgICAgICAgZm9yIChpbnQgayA9IDMsIGwgPSAoaW50KSBNYXRoLnNxcnQoaSk7IGsgPD0gbDsgayArPSAyKSB7CiAgICAgICAgICAgICAgICBpZiAoaSAlIGsgPT0gMCkgY29udGludWUgbG9vcDsKICAgICAgICAgICAgfQogICAgICAgICAgICB0ZW1wW24rK10gPSBpICogaTsKICAgICAgICB9CiAgICAgICAgZmFjdG9yID0gamF2YS51dGlsLkFycmF5cy5jb3B5T2YodGVtcCwgbik7CiAgICB9CiAgICAKICAgIHN0YXRpYyB2b2lkIHNvbHZlKGludCBuKQogICAgewogICAgICAgIGlmIChuIDwgMSkgdGhyb3cgbmV3IElsbGVnYWxBcmd1bWVudEV4Y2VwdGlvbigpOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCIlZCAtPiAlZCVuIiwgbiwgcihuLCAxLCAwKSk7CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgbG9uZyByKGludCBuLCBsb25nIGN1ciwgaW50IGYpCiAgICB7CiAgICAgICAgbG9uZyByZXQgPSBjdXI7CiAgICAgICAgZm9yIChpbnQgaSA9IGY7IGkgPCBmYWN0b3IubGVuZ3RoICYmIGN1ciAqIGZhY3RvcltpXSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgcmV0ICs9IHIobiwgY3VyICogZmFjdG9yW2ldLCBpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJldDsKICAgIH0KfQ==