けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 110 D - Factorization (400 点)

素因数分解 & 重複組合せ
を勉強できる、すごく教育的問題だった!!!

問題へのリンク

問題概要 (ABC 110 D)

整数  N, M が与えられる。

 a_1 × a_2 × ... × a_N = M

を満たす整数の組 ( a_1, a_2, ..., a_N) が何通りあるか、1000000007 で割った余りで求めよ。

制約

  •  1 \le N \le 10^{5}
  •  1 \le M \le 10^{9}

解法

素因数分解っぽいテーマの問題。こういうのは「まずは素数べきで考える」というのが 1 つの定石ではある。 p素数として

 a_1 × a_2 × ... × a_N = p^{k}

を満たす ( a_1, a_2, ..., a_N) が何通りあるかを考える。これは実は、 p の指数に着目して  a_i = p^{x_{i}} として、

 x_1 + x_2 + ... + x_N = k

を満たす 0 以上の整数 ( x_1, x_2, \dots, x_N) が何通りあるかを数え上げる問題と考えることができる。

これは重複組合せ!!!!!
重複組合せは、「仕切りを使って考える」というのが 1 つの見方ではある。


 N 個の玉と、 k-1 個の仕切りの並び替え方を数える問題


と考えることができる。

f:id:drken1215:20180923220048p:plain

例えば  N = 4, k = 9 のとき、上図のように、9 個の玉と 3 (= 4-1) 個の仕切りを並び替える問題だとみなすことができる。

 x_1 + x_2 + ... + x_N = k の解と、「玉と仕切の並び替え」とが対応する例として、下図のような感じになる。

f:id:drken1215:20180923220053p:plain

つまり場合の数は

  •  {}_{n}{\rm H}_{k} = {}_{n + k - 1}{\rm C}_{k}

である。二項係数の求め方については以前に書いた記事に書いてみた。

以上で、 M素数べきについての考察を終えたので、一般の合成数について考えることになるのだが、実は各素因子についてまったく独立に考えることができる。つまり、上記のことを各素因子ごとに独立に行って、得られた結果を掛け算していけば OK。

#include <iostream>
#include <vector>
using namespace std;

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main() {
    int N, M;
    COMinit();
    cin >> N >> M;
    auto vec = prime_factorize(M);
    long long res = 1;
    for (auto pa : vec) {
        int num = pa.second;
        long long tmp = COM(num+N-1, N-1);
        res = (res * tmp) % MOD;
    }
    cout << res << endl;
}