結果
問題 |
No.1973 Divisor Sequence
|
ユーザー |
![]() |
提出日時 | 2022-06-16 07:21:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 727 ms / 2,000 ms |
コード長 | 1,613 bytes |
コンパイル時間 | 1,067 ms |
コンパイル使用メモリ | 112,376 KB |
実行使用メモリ | 179,700 KB |
最終ジャッジ日時 | 2024-10-05 18:49:25 |
合計ジャッジ時間 | 7,156 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:67:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 67 | for(auto [i,vaku]:mp){ | ^
ソースコード
#include <iostream> #include <stdio.h> #include <cmath> #include <vector> #include <tuple> #include <bitset> #include <map> #include <queue> #include <time.h> #include <utility> #include <numeric> #include <deque> #include <cassert> #include <sstream> #include <cctype> #include <unordered_map> #include <algorithm> #include <chrono> #define ll long long #include <time.h> #define mod % 1000000007 #define rep(i,n) for(long long i = 0;i < n;i ++) ll MAX = 5'000'000'000'000'000'000LL; using namespace std; vector<ll> p; void MAKE_P(){ p = {2,3}; for(int i = 5;i <= 1000000;i ++){ bool z = true; for(ll j:p){ if(i%j==0){ z = false; break; } if(j*j>i)break; } if(z)p.push_back(i); } } int main(){ ll n,m; cin >> n >> m; if(m==1){ cout << 1 << endl; return 0; } MAKE_P(); vector<ll> q; rep(i,int(p.size())){ if(m%p[i]==0){ q.push_back(0); while(m%p[i] == 0){ q[int(q.size())-1] ++; m = m/p[i]; } } } if(m>1)q.push_back(1); map<ll,ll> mp; for(int i:q){ mp[i] = 1; } vector<ll> ans(50); for(auto [i,vaku]:mp){ if(i==0){ ans[0] = 1; continue; } vector<vector<ll>> dp(n+1,vector<ll>(i+1,0)); dp[0][0] = 1; rep(j,n){ rep(k,i+1){ dp[j][k] = dp[j][k] mod; rep(l,i+1){ if(l+k>i)break; dp[j+1][l] += dp[j][k]; } } } rep(j,i+1)ans[i] += dp[n][j]; ans[i] = ans[i] mod; } ll sum = 1; rep(i,int(q.size())){ sum = (sum*ans[q[i]]) mod; } cout << sum << endl; return 0; }