// // TODO(TLE版). // #include // using namespace std; // using LL = long long; // // // 集合S の 更新. // // @param m: 集合S. // // @return ret: 更新した集合S. // map, LL> updateSet(map, LL> m){ // map, LL> ret; // for(auto &p : m){ // vector 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 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()); // // 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 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()); // 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 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()); // 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, LL> m; // for(LL a = 1; a < sq + 1; a++){ // vector 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()); // m[v]++; // } // } // // // 2-2. N >= 3 の場合のロジック. // for(int i = 3; i <= N; i++){ // map, 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 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 getAllDivisors(LL X) { // 1. X を 2で割り切れなくなるまで割っていく. vector 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> updateSet(set> m, LL d, LL n){ // 1. 集合Sの各要素 を 巡回. set> ret; for(auto &p : m){ // 2. 素因数分解の結果を, 新しいvectorに反映. for(int i = 0; i < n; i++){ vector 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 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> m; vector v(N, 1); m.insert(v); // 各素因数に関して, 集合S へ 反映. for(auto &d : divisors){ set> 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; }