「スパイラル・ウォーク」問題

「スパイラル・ウォーク」問題

締め切りが 2016/12/22 10:00 AM なのでその 1 分後に投稿されるように予約

設問
自然数 w, h に対し、横と縦の長さがそれぞれ w, h となる格子状の道を考えます。
この左上の点からスタートして、同じ交差点を二度以上通らないように、らせんを描いて進みます。
最初は下方向にまっすぐ進み、これ以上前に進めなくなったところで左折し、再びまっすぐ進みます。
これを繰り返し、全ての交差点に到達したところで終了します。
(w, h)＝(4, 3) の場合の進み方を下に示します。このとき進んだ距離は 19 であることが分かります。



自然数 m に対し、上のように進んだ時の距離がちょうど m となるような組 (w, h) の個数を F(m) と定義します。
例えば F(11)＝4 です。進んだ距離が 11 となる組 (w, h) は、(1, 5), (2, 3), (3, 2), (5, 1) の 4 通りです。

同様に、F(3)＝1, F(23)＝6, F(28)＝0 となることが確かめられます。
さらに、自然数 n に対し、1≦m≦n となる全ての m に対する F(m) の和を G(n) と定義します。
例えば、G(11)＝12, G(100)＝283, G(1000)＝5076 となることが確かめられます。
標準入力から、自然数 n（1 ≦ n ≦ 106）が与えられます。
標準出力に G(n) を出力するプログラムを書いてください。
※ テストケースは全部で 6 つあります。全てをPASSすれば正解です。

=======================================================

行列を考えて，h 行 w 列の要素は h*w+h+w なので，(h+1)*(w+1) = h*w+h+w+1 ということから，約数の個数を求めるということに帰着できる。



つまり，F(11) は，11+1 つまり 12 の自明でない約数の個数ということ，12 の自明でない約数（1 と 12 を除く）は 2, 3, 4, 6 の 4 個で，w-1 が 2, 3, 4, 6 ということは w は 1,  2,  3,  5 それに対応する h は 5, 3, 2, 5 つまり，4 通りの格子なので，F(11) = 4。
G は，効率だけを考えてコーディング。

R で書いたけど，とても遅い。短くて簡潔なんだけどね。
AWK にしても，まだ遅い。
Java にしたら，0.5 秒ほどでできてしまった。
不公平だよね。

R プログラム

prime = function(m) {
    tbl = 1:m
    tbl[1] = 0
    for (i in 2:floor(sqrt(m))) {
        if (tbl[i]) {
            m2 = m%/%i
            tbl[2:m2 * i] = 0
        }
    }
    tbl[tbl != 0]
}

G = function(M) {
    if (M < 2) {
        return(0)
    }
    PRIME = prime(M + 1)
    sums = 0
    for (m in 1:M) {
        m = m + 1
        limit = sqrt(m)
        ans = 1
        for (i in PRIME) {

            if (i > limit) {
                ans = ans*2
                break
            }
            count = 1 # 素因子分解 i^count からの取り出し方は count+1 通り
            while (m%%i == 0) {
                m = m/i
                count = count + 1
            }
            ans = ans * count
            if (m == 1) {
                break
            }
        }
        sums = sums + ans - 2
    }
    cat(sums)
}
system.time(G(11)) # 12
system.time(G(100)) # 283
system.time(G(1000)) # 5076

system.time(G(25)) # 40
system.time(G(298)) # 1152
system.time(G(1234)) # 6518; 0.022 seq.
system.time(G(137945)) # 1377974; 6.799 seq.
system.time(G(876459)) # 10375657; 86.505 seq.
system.time(G(991245)) # 11856448; 102.718 seq.

=======================================================

AWK スクリプト

function prime(m, tbl2,     i, j, m2, count) {
    for (i = 1; m >= i; i++) {
        tbl[i] = i
    }
    tbl[1] = 0
    for (i = 2; int(sqrt(m)) >= i; i++) {
        if (tbl[i] != 0) {
            for (j = 2*i; m >= j; j +=i) {
                tbl[j] = 0
            }
        }
    }
    count = 0
    for (i = 2; m >= i; i++) {
        if (tbl[i] != 0) {
            tbl2[++count] = tbl[i]
        }
    }
    return count
}

BEGIN {
#   G(25)
#   G(298)
#   G(1234) # 6518; 0.021u
#   G(137945) # 1377974; 98.223u, 62.740u, 3.211u
#   G(876459) # 10375657; 40.984u
    G(991245) # 11856448; 53.748u
}

function G(M,      PRIME, n, sums, m, m1, m2, ans, i, p, count) {
    if (M < 2) {
        return 0
    }
    n = prime(M+1, PRIME)
    sums = 0
    for (m = 1; M >= m; m++) {
        m1 = m + 1
        m2 = sqrt(m1)
        ans = 1
        for (i = 1; n >= i; i++) {
            p = PRIME[i]
            if (p > m2) {ans *= 2; break}
            count = 1
            while (m1%p == 0) {
                m1 /= p
                count = count + 1
            }
            ans = ans * count
            if (m1 == 1) {
                break
            }
        }
        sums += ans - 2
    }
    print sums
}

#{G($0)}

=======================================================

Java プログラム

import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String line;
        line =cin.nextLine();
        int M = Integer.parseInt(line);
        G(M);
    }

    static int[] prime(int m) {
        int i, j, count;
        int[] tbl = new int[m + 1];
        int[] tbl2 = new int[m + 1];
        for (i = 1; m >= i; i++) {
            tbl[i] = i;
        }
        tbl[1] = 0;
        for (i = 2; Math.sqrt(m) >= i; i++) {
            if (tbl[i] != 0) {
                for (j = 2 * i; m >= j; j += i) {
                    tbl[j] = 0;
                }
            }
        }
        count = 0;
        for (i = 2; m >= i; i++) {
            if (tbl[i] != 0) {
                tbl2[++count] = tbl[i];
            }
        }
        return tbl2;
    }

    static void G(int M) {
        int n, sums, m, m1, m2, ans, i, p, count;
        int[] PRIME = new int[M + 1];
        if (M < 2) {
            return;
        }
        PRIME = prime(M + 1);
        n = PRIME.length;
        sums = 0;
        for (m = 1; M >= m; m++) {
            m1 = m + 1;
            m2 = (int) Math.sqrt(m1);
            ans = 1;
            for (i = 1; n >= i; i++) {
                p = PRIME[i];
                if (p > m2) {
                    ans *= 2;
                    break;
                }
                count = 1;
                while (m1 % p == 0) {
                    m1 /= p;
                    count++;
                }
                ans *= count;
                if (m1 == 1) {
                    break;
                }
            }
            sums += ans - 2;
        }
        System.out.println(sums);
    }
}