結果
問題 |
No.1659 Product of Divisors
|
ユーザー |
![]() |
提出日時 | 2023-01-16 21:23:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 1,418 bytes |
コンパイル時間 | 1,242 ms |
コンパイル使用メモリ | 111,892 KB |
最終ジャッジ日時 | 2025-02-10 03:56:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> #include <complex> #include <cassert> using namespace std; const long long modc = 1e9+7; long long mod_exp(long long b){ long long e = modc-2; if (e > 0 && b == 0) return 0; long long ans = 1; b %= modc; while (e > 0){ if ((e & 1)) ans = (ans * b) % modc; e = e>>1; b = (b*b) % modc; } return ans; } long long C(long long n, long long k){ long long ans=1; for(long long i=0; i<k; i++) ans = ans * (n-i) % modc; for(long long i=1; i<=k; i++) ans = (ans*mod_exp(i)) % modc; return ans; } map<long long, long long> prime; void prime_factor(long long n){ long long m = n; if (n % 2 == 0){ while(n % 2 == 0){ prime[2]++; n /= 2; } } for (long long i = 3; i*i <= m; i+=2){ if (n % i == 0){ while(n % i == 0){ prime[i]++; n /= i; } } } if (n != 1){ prime[n]++; } } int main(){ long long ans=1, N, K; cin >> N >> K; prime_factor(N); K %= modc; for (auto [x, y] : prime){ ans *= C(K+y, y); ans %= modc; } cout << ans << endl; return 0; }