結果

問題 No.473 和と積の和
ユーザー @abcde@abcde
提出日時 2019-05-10 22:39:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,538 bytes
コンパイル時間 1,848 ms
コンパイル使用メモリ 180,524 KB
実行使用メモリ 493,340 KB
最終ジャッジ日時 2023-09-14 18:02:06
合計ジャッジ時間 12,551 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 319 ms
63,904 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 4 ms
4,376 KB
testcase_25 AC 2,845 ms
421,592 KB
testcase_26 AC 203 ms
41,632 KB
testcase_27 AC 368 ms
68,024 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 33 ms
4,864 KB
testcase_30 AC 28 ms
4,512 KB
testcase_31 AC 19 ms
4,552 KB
testcase_32 AC 14 ms
4,376 KB
testcase_33 AC 4 ms
4,380 KB
testcase_34 TLE -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// // 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;
    
}
0