Atcoder ARC #004 D. 表現の自由 ( Freedom of expression )

Atcoder ARC #004 D. 表現の自由 ( Freedom of expression )

D: 表現の自由 ( Freedom of expression ) - AtCoder Regular Contest 004 | AtCoder

整数nをm個の整数の積で表す方法の数を求める問題。

真っ先に考えたのは、負の数をどう処理するかであった。とりあえず数値は無視して、全体の符号について考えてみる。例えば、全体の符号を正にしたいとすると各符号はどうなるだろうか？実はm個のうちm - 1個はどちらの符号になっていても構わないことがわかる。なぜなら、最後の1個の符号をm - 1個の積の符号と同じにすれば、全体の符号は正になるからである。逆にそれによってすべての正負のパターンを網羅できることもいえるはずである。また、(-n, m)=(n, m)であることも示せるので、結局すべて正として考えてよく、最後に2のm - 1乗をかけてやればよいことになる。すべて正とすると、あとはm個の箱を用意して、nの素因数たちを分配していくとよい。重複を許してすべての素因数を分配すればよいので、これをm個の箱から、重複を許して(素因数の数)個の箱を選ぶ、と読み替えて、積をとっていくだけでよいことになる。つまり、ライブラリをペタリとはりつけるだけでよいことになる。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)

static const int MOD = 1000000007;
#define int long long

long long inv(long long x) {
        long long  y = 1;
        while (y % x) y += MOD;
        return y / x;
}

long long nCr(long long n, long long r) {
        if (n < r) return 0;
        if (n - r < r) r = n - r;
        long long ret = 1;
        rep(i, r) {
                ret = ret * n % MOD;
                n --;
                ret = ret * inv(i + 1) % MOD;
        }
        return ret;
}

long long nHr(long long n, long long r) {
        return nCr(n + r - 1, r);
}

signed main() { 
        int n, m;
        cin >> n >> m;
        n = n < 0 ? -n : n; //nが負ならば正にする
        int ans = 1;
        for (int i = 2; i * i <= n; i ++) if (n % i == 0) {
                int cnt = 0;
                while (n % i == 0) {
                        n /= i;
                        cnt ++;
                }
                ans = ans * nHr(m, cnt) % MOD;//m個の箱にcnt個のある素因数を分配する方法の数をかける
        }
        if (n > 1) ans = ans * nHr(m, 1) % MOD;
        rep(i, m - 1) ans = ans * 2 % MOD; //2のm - 1乗をかける
        cout << ans << endl;
        return 0;
}