結果
問題 |
No.473 和と積の和
|
ユーザー |
|
提出日時 | 2019-11-07 20:07:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 3,000 ms |
コード長 | 1,294 bytes |
コンパイル時間 | 1,007 ms |
コンパイル使用メモリ | 103,824 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-25 05:14:44 |
合計ジャッジ時間 | 3,350 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>#include <limits>static const int MOD = 1000000007;using ll = long long;using u32 = uint32_t;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;template<class T>vector<T> divisor(T n){vector<T> ret;for(T i = 1; i * i <= n; i++) {if(n % i == 0) {ret.push_back(i);if(i * i != n) ret.push_back(n / i);}}sort(begin(ret), end(ret));return(ret);}int main() {int n, x;cin >> n >> x;x++;int ans = 0;auto v = divisor(x);int m = v.size();vector<vector<int>> divisors(m);for (int i = 0; i < m; ++i) {for (int j = i-1; j >= 0; --j) {if(v[i]%v[j] == 0) divisors[i].emplace_back(j);}}auto dfs = [&](int x, int dep, int ub, auto &&f) -> void {if(x == 0) {if(dep == n) ans++;return;}for (auto &&i : divisors[x]) {if(ub < v[x]/v[i]) return;f(i, dep+1, v[x]/v[i], f);}};dfs(m-1, 0, x, dfs);cout << ans << "\n";return 0;}