ABC052/ARC067: C - Factors of Factorial

競技プログラミング 素数 素因数分解 約数

問題

問題文

問題概要

整数 N が与えらる.

N! の正の約数の個数を 10^{9}+7 割った余りを求めよ.

制約

  • 1 \leqq N \leqq 1000

解答例

指針

  • N = p_1^{e_1} \times p_2^{e_2} \times \cdot \cdot \cdot \times p_n^{e_n} とすると,
  • \text{Nの正の約数の個数} = (e_1+1) \times (e_2+1) \times \cdot \cdot \cdot \times (e_n+1)

解説

N = p_1^{e_1} \times p_2^{e_2} \times \cdot \cdot \cdot \times p_n^{e_n} と素因数分解すると,

\displaystyle \text{Nの正の約数の個数} = \prod_{k=1}^n (e_k + 1) = (e_1+1) \times (e_2+1) \times \cdot \cdot \cdot \times (e_n+1) となる.

なぜ, これが成り立つかの説明は以下のサイトがわかりやすい.

1 から N をそれぞれ素因数分解し, 指数部の値を累積させて, 上記の式における e_k を求める.

実装は以下のように, 素因数分解したときの素数 p の指数部を exps[p] のように配列でもつと楽.

1 \leqq N \leqq 1000 なので, N! の素因数のさ最大値は 1000 以下となる.

  • C++ による実装例
// submission: https://atcoder.jp/contests/abc052/submissions/8679551
// lang:       C++14 (GCC 5.4.1)
// time:       1 ms
// memory:     256 KB

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
  int n;
  cin >> n;

  int exps[1003] = {0};
  const ll mod = int(1e9) + 7;

  for (int i = 2; i <= n; i++) {
    int t = i, div = 2;
    while ( div*div <= i ) {
      if (t % div == 0) {
        exps[div]++;
        t /= div;
      } else {
        div++;
      }
    }
    if (t != 1) { exps[t]++; }
  }

  ll ans = 1;
  for (int i = 2; i <= n; i++) {
    ans *= (exps[i] + 1);
    ans %= mod;
  }

  cout << ans << endl;

  return 0;
}
  • Python3 による実装例
# submission: https://atcoder.jp/contests/abc052/submissions/8679557
# lang:       Python3 (3.4.3)
# time:       23 ms
# memory:     3064 KB

n = int(input())
exps = [0] * 1003

for i in range(2, n+1):
    t = i
    div = 2
    while div*div <= i:
        if t % div == 0:
            exps[div] += 1
            t //= div
        else:
            div += 1
    if t != 1:
        exps[t] += 1

ans = 1
mod = int(1e9) + 7

for i in range(2, n+1):
    ans *= (exps[i] + 1)
    ans %= mod

print(ans)
  • Go による実装例
// submission: https://atcoder.jp/contests/abc052/submissions/8679564
// lang:       Go (1.6)
// time:       1 ms
// memory:     512 KB

package main

import "fmt"

func main() {
        var n int
        fmt.Scan(&n)

        var exps [1003]int

        for i := 0; i <= n; i++ {
                t := i
                div := 2
                for div*div <= i {
                        if t%div == 0 {
                                t /= div
                                exps[div]++
                        } else {
                                div++
                        }
                }
                if t != 1 {
                        exps[t]++
                }
        }

        var ans int64 = 1
        const mod = int64(1e9) + 7

        for i := 2; i <= n; i++ {
                ans *= int64(exps[i] + 1)
                ans %= mod
        }
        fmt.Println(ans)
}

以下のように, 素因数分解のライブラリを使って実装してもよい. (素因数分解の実装は蟻本を参考にした)

  • C++ による実装例
// submission: https://atcoder.jp/contests/abc052/submissions/8691145
// lang:       C++14 (GCC 5.4.1)
// time:       2 ms
// memory:     256 KB

#include <iostream>
#include <map>

using namespace std;

typedef long long ll;

map<ll, int> prime_factor(ll n) {
  map<ll, int> ret;
  for (ll i = 2; i*i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) { ret[n]++; }
  return ret;
}

int main() {
  int n;;
  cin >> n;

  map<int, int> mp;

  for (int i = 2; i <= n; i++) {
    map<ll, int> mp_t = prime_factor(i);
    for (auto it = mp_t.begin(); it != mp_t.end(); it++) {
      mp[it->first] += (it->second);
    }
  }

  ll ans = 1;
  ll mod = (1e9)+7;

  for (auto it = mp.begin(); it != mp.end(); it++) {
    ans *= ((it->second)+1);
    ans %= mod;
  }

  cout << ans << endl;

  return 0;
}
  • Python3 による実装例
# submission: https://atcoder.jp/contests/abc052/submissions/8691158
# lang:       Python3 (3.4.3)
# time:       21 ms
# memory:     3064 KB

def prime_factor(n):
    ret = {}
    p = 2

    while p*p <= n:
        while n % p == 0:
            ret[p] = ret.get(p, 0) + 1
            n //= p
        p += 1

    if n != 1: ret[n] = 1

    return ret

n = int(input())
d = {}

for i in range(2, n+1):
    t = prime_factor(i)
    for k, v in t.items():
        d[k] = d.get(k, 0) + v

ans = 1
mod = int(1e9) + 7

for _, v in d.items():
    ans *= (v+1)
    ans %= mod

print(ans)
  • Go による実装例
// submission: https://atcoder.jp/contests/abc052/submissions/8691189
// lang:       Go (1.6)
// time:       2 ms
// memory:     768 KB

package main

import "fmt"

func prime_factor(n int64) map[int64]int {
    ret := map[int64]int{}

    for i := int64(2); i*i <= n; i++ {
        for n%i == 0 {
            ret[i]++
            n /= i
        }
    }
    if n != 1 {
        ret[n]++
    }
    return ret
}

func main() {
    var n int64
    fmt.Scan(&n)

    mp := make(map[int64]int)

    for i := int64(2); i <= n; i++ {
        t := prime_factor(i)
        for k, v := range t {
            mp[k] += v
        }
    }

    var ans int64 = 1
    mod := int64(1e9) + 7

    for _, v := range mp {
        ans *= int64(v + 1)
        ans %= mod
    }

    fmt.Println(ans)
}

感想

素因数分解して約数の数を数えるのは小学生の頃よくやった記憶がある.

参考文献