結果
問題 |
No.1659 Product of Divisors
|
ユーザー |
|
提出日時 | 2021-08-27 21:35:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 2,718 bytes |
コンパイル時間 | 4,430 ms |
コンパイル使用メモリ | 234,256 KB |
実行使用メモリ | 15,748 KB |
最終ジャッジ日時 | 2024-12-20 15:59:28 |
合計ジャッジ時間 | 7,130 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define all(x) (x).begin(),(x).end() const long long MOD = 1000000007; const long long INF = 9*1e18; using ll = long long; using mint = modint1000000007; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } long double PI = 3.14159265358979; ll fac[510000], finv[510000], inv[510000]; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i < 510000; 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; } } ll COM(ll n, ll k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } vector<ll> primelist; bool Prime(ll num) { if (num < 2) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; double sqrtNum = sqrt(num); for (ll i = 3; i <= sqrtNum; i += 2) { if (num % i == 0) { return false; } } return true; } void primeinput(){ for(ll i = 2;i<200200;i++){ if(Prime(i)){ primelist.push_back(i); } } } vector <ll> bunkai(ll N){ vector <ll> res; rep(i,primelist.size()){ while(N%primelist[i] == 0){ res.push_back(primelist[i]); N/=primelist[i]; } } if(N!=1){ res.push_back(N); } return res; } long long pow(long long x, long long n, long long MM) { long long ret = 1; while (n > 0) { if (n & 1) ret = ret * x % MM; // n の最下位bitが 1 ならば x^(2^i) をかける x = x * x % MM; n >>= 1; // n を1bit 左にずらす } return ret; } mint comb(ll N,ll K){ mint t = 1; for(int i = 0;i<K;i++){ t *= N; N--; } ll te = K; for(int i = 0;i<K;i++){ t /= te; te--; } return t; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); ll N,K; cin>>N>>K; if(N == 1){ cout << 1 << endl; return 0; } primeinput(); COMinit(); vector<ll> S = bunkai(N); sort(all(S)); vector<ll> num; ll temp = 1; for(int i = 1;i<S.size();i++){ if(S[i] == S[i-1]){ temp++; } else{ num.push_back(temp); temp = 1; } } num.push_back(temp); mint ans = 1; rep(i,num.size()){ ll T = num[i]; mint temp = 0; for(int k = 0;k<=T;k++){ temp += comb(K+k-1,k); } ans *= temp; } cout << ans.val() << endl; return 0; }