結果
| 問題 |
No.473 和と積の和
|
| コンテスト | |
| ユーザー |
 @abcde
|
| 提出日時 | 2019-05-10 22:39:07 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,538 bytes |
| コンパイル時間 | 1,914 ms |
| コンパイル使用メモリ | 181,124 KB |
| 実行使用メモリ | 495,520 KB |
| 最終ジャッジ日時 | 2024-07-02 01:05:16 |
| 合計ジャッジ時間 | 10,923 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 30 TLE * 1 -- * 12 |
ソースコード
// // TODO(TLE版).
// #include <bits/stdc++.h>
// using namespace std;
// using LL = long long;
//
// // 集合S の 更新.
// // @param m: 集合S.
// // @return ret: 更新した集合S.
// map<vector<LL>, LL> updateSet(map<vector<LL>, LL> m){
// map<vector<LL>, LL> ret;
// for(auto &p : m){
// vector<LL> v = p.first;
// // for(auto &x : v){
// // LL sq = sqrt(x + 0.0) + 1;
// // for(LL a = 1; a < sq + 1; a++){
// // LL b = (x - a) / (1 + a);
// // if(b > 0 && a + b + a * b == x){
// // vector<LL> lv = v;
// // lv.erase(remove(lv.begin(), lv.end(), x), lv.end());
// // lv.push_back(a);
// // lv.push_back(b);
// // sort(lv.begin(), lv.end(), greater<LL>());
// // ret[lv]++;
// // }
// // }
// // }
// // v[0]のみ確認する方針に変更.
// LL x = v[0];
// LL sq = sqrt(x + 0.0) + 1;
// // 偶数の場合.
// if(x % 2 == 0){
// for(LL a = 2; a <= sq + 1; a += 2){
// LL b = (x - a) / (1 + a);
// if(b > 1 && a + b + a * b == x){
// vector<LL> lv = v;
// lv.erase(remove(lv.begin(), lv.end(), x), lv.end());
// lv.push_back(a);
// lv.push_back(b);
// sort(lv.begin(), lv.end(), greater<LL>());
// ret[lv]++;
// }
// }
// }
// // 奇数の場合.
// if(x % 2 == 1){
// for(LL a = 1; a <= sq + 1; a++){
// LL b = (x - a) / (1 + a);
// if(b > 0 && a + b + a * b == x){
// vector<LL> lv = v;
// lv.erase(remove(lv.begin(), lv.end(), x), lv.end());
// lv.push_back(a);
// lv.push_back(b);
// sort(lv.begin(), lv.end(), greater<LL>());
// ret[lv]++;
// }
// }
// }
// }
// return ret;
// }
//
// int main() {
//
// // 1. 入力情報取得.
// LL N, X;
// // cin >> N >> X;
// scanf("%llu %llu", &N, &X);
//
// // 2. N >= 30 の 場合は, 存在しないと判定.
// // 2 の 30乗 = 1073741824 > 1e9 であるため.
// LL ans = 0;
// if(N >= 30){
// cout << ans << endl;
// return 0;
// }
//
// // 2. 条件を満たす 集合S を 探索.
// // 2-1. N = 2 の場合のロジック.
// LL sq = sqrt(X + 0.0) + 1;
// map<vector<LL>, LL> m;
// for(LL a = 1; a < sq + 1; a++){
// vector<LL> v;
// LL b = (X - a) / (1 + a);
// if(b > 0 && a + b + a * b == X){
// v.push_back(a);
// v.push_back(b);
// sort(v.begin(), v.end(), greater<LL>());
// m[v]++;
// }
// }
//
// // 2-2. N >= 3 の場合のロジック.
// for(int i = 3; i <= N; i++){
// map<vector<LL>, LL> lm = updateSet(m);
// swap(m, lm);
// }
// // for(auto &p : m){
// // auto v = p.first;
// // for(auto &i : v) cout << i << " ";
// // cout << endl;
// // }
//
// // 4. 出力 ～ 後処理.
// // ex.
// // 29 805306367
// // 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
// // -> の 1通り と思われる.
// // 14 147026879
// // -> の 1通り と思われる(3351[ms] かかったので, TLE確定).
// // 16 147026879
// // -> の 0通り と思われる(2961[ms] かかったので, TLE確定).
// // for(auto &p : m) if(p.first.size() == N) ans++;
// // cout << ans << endl;
// ans = m.size();
// printf("%llu\n", ans);
// return 0;
//
// }
// TODO(速度改善版).
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return: 素因数分解 の 結果 を 返却.
vector<LL> getAllDivisors(LL X) {
// 1. X を 2で割り切れなくなるまで割っていく.
vector<LL> ret;
while(X % 2 == 0) ret.push_back(2), X >>= 1;
// 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
for(LL i = 3; i <= sqrt(X); i += 2){
while(X % i == 0){
ret.push_back(i);
X /= i;
}
}
// 3. X が 2 より 大きな素数であれば, 追加.
if(X > 2) ret.push_back(X);
// 4. 出力.
return ret;
}
// 集合S の 更新.
// @param m: 集合S.
// @param d: 正整数Xを素因数分解した結果から取得した素因数.
// @param n: 集合Sの各要素サイズ.
// @return ret: 更新した集合S.
set<vector<LL>> updateSet(set<vector<LL>> m, LL d, LL n){
// 1. 集合Sの各要素 を 巡回.
set<vector<LL>> ret;
for(auto &p : m){
// 2. 素因数分解の結果を, 新しいvectorに反映.
for(int i = 0; i < n; i++){
vector<LL> v = p;
v[i] *= d;
sort(v.begin(), v.end());
ret.insert(v);
}
}
// cout << "updateSet d=" << d << endl;
// for(auto &p : ret){
// for(auto &v : p) cout << v << " ";
// cout << endl;
// }
// 3. 結果を返却.
return ret;
}
int main() {
// 1. 入力情報取得.
LL N, X;
// cin >> N >> X;
scanf("%llu %llu", &N, &X);
// 2. X + 1 を 素因数分解.
// -> 速度改善が上手く行かなかったので, 解答方針を変更.
// -> (a + 1) * (b + 1) = X + 1 の因数分解をベースに考える.
vector<LL> divisors = getAllDivisors(X + 1);
// ex.
// 147026879 + 1 = 147026880
// = 2 * 2 * 2 * 2 * 2 * 2 * 3 * 3 * 3 * 5 * 7 * 11 * 13 * 17
// for(auto &p : divisors) cout << p << " ";
// 3. 素因数分解の結果から, (a + 1, b + 1) の組み合わせを全列挙するイメージ.
LL ans = 0;
LL d = divisors.size();
// 3-1. 集合S の 要素サイズ(N) が大きすぎる場合は, 0個.
if(N > d){
cout << ans << endl;
return 0;
}
// 4. 要素 d個をグループ N個に分割.
set<vector<LL>> m;
vector<LL> v(N, 1);
m.insert(v);
// 各素因数に関して, 集合S へ 反映.
for(auto &d : divisors){
set<vector<LL>> lm = updateSet(m, d, N);
swap(m, lm);
}
// 5. 出力 ～ 後処理.
for(auto &p : m){
bool isOne = false;
for(auto &v : p){
if(v == 1){
isOne = true;
break;
}
}
// 集合S の 要素で, 1 を含むものは, カウント対象から外す.
if(!isOne) ans++;
}
// ex.
// 29 805306367
// -> 1通り と思われる(347[ms] かかった).
// 6 147026879
// -> 147520通り(323[ms] かかった).
// 14 147026879
// -> 1通り と思われる(1012[ms] かかったので, ぎりぎり耐えられるかどうか).
// 16 147026879
// -> 0通り と思われる(2[ms] かかった).
printf("%llu\n", ans);
return 0;
}