結果
問題 |
No.473 和と積の和
|
ユーザー |
![]() |
提出日時 | 2016-12-23 04:00:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 3,000 ms |
コード長 | 1,014 bytes |
コンパイル時間 | 1,704 ms |
コンパイル使用メモリ | 180,620 KB |
実行使用メモリ | 18,688 KB |
最終ジャッジ日時 | 2024-12-16 04:21:17 |
合計ジャッジ時間 | 3,075 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; int id[1500][1500], dp[1500][1500]; int main() { int n, x; cin >> n >> x; ++x; if (n > 30 || x < 1 << n) { printf("0\n"); return 0; } vector<int> yak; for (int i = 1; i * (long long)i <= x; i++) { if (x % i == 0) { yak.emplace_back(i); if (x / i > i) yak.emplace_back(x / i); } } sort(yak.begin(), yak.end()); int c = yak.size(); unordered_map<int, int> m; for (int i = 0; i < c; i++) { m[yak[i]] = i; for (int j = 0; j <= i; j++) id[i][j] = yak[i] % yak[j] > 0 ? 0 : m[yak[i] / yak[j]]; } for (int i = 1; i < c; i++) for (int j = i; j < c; j++) dp[i][j] = 1; for (int i = 0; i < n - 1; i++) for (int j = c - 1; j > 0; j--) for (int k = 1; k < c; k++) dp[j][k] = dp[j][k - 1] + dp[id[j][k]][k]; cout << dp[c - 1][c - 1] << "\n"; return 0; }