「ディビジョン・サム」問題

「ディビジョン・サム」問題

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

設問
自然数 n に対し、(n！)^n　（つまり n の階乗の n 乗）の約数の和を F(n) と定義します。
例えば、F(2) ＝ 7 です。(2！)^2 ＝ 4 で、4 の約数は 1, 2, 4 だからです。
また、F(3) ＝ 600 です。(3！)^3 ＝ 216 で、216 には 16 個の約数があり、それらの和は 600 です。
同様に、F(4) ＝ 991111となります。
標準入力から、自然数 n（1 ≦ n ≦ 103）が与えられるとき、
標準出力に F(n) を 1000003 で割った余り を出力するプログラムを書いてください。
たとえば、
F(12) を1000003で割った余りは845575となります。

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

R で書くと F(997) が時間オーバーになった
AWK で書き，bash で gawk を起動すれば，制限時間内で答えが出た

M  = 1000003
divisor = function(n) {
    if (n%%2 == 0)
        return(2)
    else if (n%%3 == 0)
        return(3)
    maxitr = as.integer(sqrt(n))
    i = 1
    repeat {
        i = i + 4
        if (i > maxitr)
            return(n)
        else if (n%%i == 0)
            return(i)
        i = i + 2
        if (i > maxitr)
            return(n)
        else if (n%%i == 0)
            return(i)
    }
}

factorization = function(n) {
    result = NULL
    repeat {
        div = divisor(n)
        result = c(result, div)
        n = n/div
        if (n == 1)
            return(result)
    }
}

prod = function(b, a) {
    result = term = 1
    for (i in 1:a) {
        term = (term*b) %% M
        result = (result+term)
    }
    result %% M
}

F = function(n) {
    result = NULL
    for (i in 2:n) {
        result = c(result, factorization(i))
    }
    a = n*table(result)
    b = as.integer(names(a))
    ans = 1
    for (i in seq_along(a)) {
        ans = (ans*prod(b[i], a[i])) %% M
    }
    cat(ans %% M)
}
# F(4) # 991111
# F(12) # 845575
# F(11) # 687005
# F(99) # 820272
# F(264) # 398251
# F(610) # 823587
# F(912) # 210178
# F(997) # 772380

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

awk

function divisor(n,     i, maxitr) {
  if (n%2 == 0) return 2
  else if (n%3 == 0) return 3
  maxitr = int(sqrt(n))
  i = 1
  for (;;) {
    i = i + 4
    if (i > maxitr) return n
    else if (n%i == 0) return i
    i = i + 2
    if (i > maxitr) return n
    else if (n%i == 0) return i
  }
}

function factorization(n, result,    div) {
  for (;;) {
    div = divisor(n)
    result[div]++
    n = n/div
    if (n == 1) return
  }
}

function prod(b, a,     result, term, i, M) {
  M = 1000003
  result = term = 1
  for (i = 1; a >= i; i++) {
    term = term*b % M
    result = result+term
  }
 return result % M
}

function F(n,       i, res, fac, result, ans, b, M) {
  M = 1000003
  for (i = 2; n >= i; i++) {
    factorization(i, res)
    for (fac in res) {
      result[fac] += res[fac]
      delete res[fac]
    }
  }
  ans = 1
  for (b in result) {
    ans = (ans*prod(b, n*result[b])) % M
  }
  print ans % M
}

不要なスペース除去

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

求められるプログラムの前提条件は、以下の通りとなります。

    標準入力から、英数字、スペース、句読点（後述）のいずれかのみで構成された英文が送られる
    文字列の長さは80以下とする
    文字列の先頭および末尾から続くスペースは除去の対象する
    先頭および末尾を処理した文字列の中で、2文字以上連続するスペースは、1スペースを残し、残るスペースは除去の対象とする
    句読点はピリオド(.)、カンマ(,）、疑問符(?)のいずれかとし、句読点の直前にあるスペースは除去対象とする
    上記ルールにもとづき、スペースを除去した文字列を標準出力に返すこと

以下、整形例となります。

【入出力サンプル】
標準入力
  Hello  ,  CodeIQ.  

標準出力
Hello, CodeIQ.

==========

「○○となります」ってのは，気味悪いから，止しにしてくれ。
なお，テスト入力例が，プログラムの仕様をチェックするために十分なものでないのが納得いかねえ。

f = function(s) {
    s = sub("^ +", "", s)
    s = sub(" +$", "", s)
    s = gsub("  +", " ", s)
    s = gsub(" +([,.?])", "\\1", s)
    cat(s)
}