Submission #5383696

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
#include <iomanip>
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
constexpr int MOD = 1000000007;
//http://drken1215.hatenablog.com/entry/2018/09/29/180900
void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}
//素因数分解
//ある数の指数乗で表す
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));//nが素数だった場合
    return res;
}

ll modpow(ll a,ll p){
    if(p==0) return 1;
    if(p%2==0){
        ll halfp = p/2;
        ll half = modpow(a,halfp);
        return half * half % MOD;
    }else{
        return a * modpow(a,p-1) % MOD;
    }
}

ll calcComb(ll a,ll b){
    if (b > a-b){
        return calcComb(a,a-b);
    }
    ll ansMul = 1;
    ll ansDiv = 1;
    REP(i,b){
        ansMul *= (a - i);
        ansDiv *= (i + 1);
        ansMul %= MOD;
        ansDiv %= MOD;
    }
    ll ans = ansMul * modpow(ansDiv,MOD-2) ;
    ans %= MOD;
    return ans;
}

int main ()
{
    int N,M;
    cin>>N>>M;
    auto vec = prime_factorize(abs(N));
    ll res = 1;
    for (auto pa:vec){
        int k = pa.second;
        ll tmp = calcComb(M+k-1,k);
        res = (res * tmp) % MOD;
    }
    //2のm-1乗る
    res = res * modpow(2LL,M-1) % MOD;
    cout<<res<<endl;
    return 0;
}

Submission Info

Judge Result