結果
問題 | No.1659 Product of Divisors |
ユーザー |
|
提出日時 | 2021-08-27 22:13:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 1,715 ms |
コンパイル使用メモリ | 122,552 KB |
最終ジャッジ日時 | 2025-01-24 03:13:58 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#pragma GCC optimize("Ofast") #include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <cstdio> #include <ctime> #include <assert.h> #include <chrono> #include <random> #include <numeric> #include <set> #include <deque> #include <stack> #include <sstream> #include <utility> #include <array> using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } constexpr ll mod = 1e9+7; ll mod_pow(ll a,ll b){ a%=mod; if(b==0)return 1; if(b==1)return a; ll res=mod_pow(a,b/2)%mod; res*=res; res%=mod; if(b%2)res*=a; return res%mod; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n,k; cin >> n >> k; // binom(n-1+k,k) auto comb=[&](ll n,ll k)->ll{ ll res = 1; for(ll i=1;i<=k;i++){ res *= (n+1-i)%mod; res %= mod; res *= mod_pow(i,mod-2); res %= mod; } return res; }; ll res = 1; for(ll i=2;i*i<=n;i++){ if(n%i==0){ int cnt=0; while(n%i==0){ n/=i; cnt++; } ll sum = 1; for(int j=1;j<=cnt;j++){ sum += comb(k-1+j, j); sum %= mod; } res *= sum; res %= mod; } } if(n > 1){ res *= (1+comb(k, 1)); res %= mod; } cout << res << endl; }