結果

問題 No.3115 One Power One Kill
ユーザー k1suxu
提出日時 2025-04-20 02:08:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 7,820 bytes
コンパイル時間 4,005 ms
コンパイル使用メモリ 288,500 KB
実行使用メモリ 25,868 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-04-20 02:09:10
合計ジャッジ時間 7,483 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘std::vector<std::vector<long long int> > Random::tree_generator_using_prufer_code()’:
main.cpp:140:61: warning: no return statement in function returning non-void [-Wreturn-type]
  140 |     vector<vector<int>> tree_generator_using_prufer_code() {}
      |                                                             ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using std::cin;
using std::cout;

#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define all(x) x.begin(),x.end()
//#define mp make_pair
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>

template<typename T>
bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}}
template<typename T>
bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}}

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll INF = numeric_limits<long long>::max() / 2;
const ld pi = 3.1415926535897932384626433832795028;
const ll mod = 1e9 + 7;
int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};

#define int long long

struct fast_prime_factorize {
private:
    vector<int> MinFactor;
    vector<bool> IsPrime;
public:
    vector<int> primes;
    
    fast_prime_factorize(const int MAXN) : MinFactor(MAXN), IsPrime(MAXN) {
        for (int i = 0; i < MAXN; ++i) IsPrime[i] = true, MinFactor[i] = -1;
        IsPrime[0] = false; IsPrime[1] = false; 
        MinFactor[0] = 0; MinFactor[1] = 1;
        for (int i = 2; i < MAXN; ++i) {
            if (IsPrime[i]) {
                MinFactor[i] = i;
                primes.push_back(i);
                for (int j = i*2; j < MAXN; j += i) {
                    IsPrime[j] = false;
                    if (MinFactor[j] == -1) MinFactor[j] = i;
                }
            }
        }
    }

    vector<pair<int,int> > factorize(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = MinFactor[n];
            int exp = 0;
            while (MinFactor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }

    bool is_prime(int n) {
        return IsPrime[n];
    }
    vector<int> All_Min_Factor() {
        return MinFactor;
    }
    vector<int> All_Primes() {
        return primes;
    }
}sieve(100100);

struct Random {
private:
    struct UnionFind {
        vector<int> r;
        
        UnionFind(int n) {
            r = vector<int>(n, -1);
        }

        int root(int x) {
            if(r[x] < 0) return x;
            return r[x] = root(r[x]);
        }

        bool unite(int x, int y) {
            x = root(x);
            y = root(y);
            if(x == y) return false;
            if(r[x] > r[y]) swap(x, y);
            r[x] += r[y];
            r[y] = x;
            return true;
        }

        bool issame(int x, int y) {
            return root(x) == root(y);
        }
    };

public:
    mt19937_64 rng;
    Random() {
        random_device rnd;
        srand((int)time(0));
        rng = mt19937_64(rnd() * rand());
    }

    vector<vector<int>> tree_generator_using_UF(const int n, const int indexed=0) {
        UnionFind UF(n+indexed);
        vector<vector<int>> g(n+indexed);
        int edge_count = 0;

        while(edge_count < n-1) {
            int u = rng()%n+indexed;
            int v = rng()%n+indexed;

            if(!UF.issame(u, v)) {
                g[u].push_back(v);
                g[v].push_back(u);
                UF.unite(u, v);
                ++edge_count;
            }
        }
        return g;
    }

    vector<vector<int>> tree_generator_using_prufer_code() {}

    // return random non-negative integer in [l, r)
    int get_int(int l, int r) {
        return rng()%(r-l)+l;
    }

    // return random array consisting of non-negatove integer in [l, r)
    vector<int> get_array(const int len, const int l, const int r) {
        vector<int> x;
        for(int i = 0; i < len; ++i) {
            x.push_back(get_int(l, r));
        }
        return x;
    }

    // not debugged (might contain some bugs)
    vector<int> get_permutation(const int len, int start_val = 0) {
        vector<int> x(len);
        iota(all(x), start_val);
        shuffle(x.begin(), x.end(), rng);
        return x;
    }

    string get_string(const int len, bool lower, bool upper, bool number) {
        vector<char> char_set;
        if(lower) for(int i = 0; i < 26; i++) char_set.push_back((char)('a' + i));
        if(upper) for(int i = 0; i < 26; i++) char_set.push_back((char)('A' + i));
        if(number) for(int i = 0; i < 9; i++) char_set.push_back((char)('0' + i));
        return get_string(len, char_set);
    }

    string get_string(const int len, vector<char> char_set) {
        string s;
        for(int i = 0; i < len; i++) s.push_back(char_set[get_int(0, (int)char_set.size())]);
        return s;
    }

    void my_sleep(const int millisec) {
        std::this_thread::sleep_for(std::chrono::milliseconds(millisec));
    }
} rd;

template<typename T_VAL, typename T_EXP>
T_VAL modpow(T_VAL n, T_EXP m, const T_VAL MOD) {
    // // basically (default), 0^0=1
    // // 0^0 = 0にしたいなら以下の行が必要
    // if(n == 0) return 0;
    T_VAL res = 1;
    while(m > 0) {
        if(m&1) res = (res*n)%MOD;
        n = (n*n)%MOD;
        m >>= 1;
    }
    return res;
}

void solve() {
    // gcdがbの倍数だと困る
    int a = 89856, b = 2592;
    cout << a << " " << b << endl;

    const int MAX = 1e5 + 1;
    vector<int> gcds(MAX, -1);
    int y = modpow(a, b, mod);
    bool flg = true;
    repi(i, 100, MAX) {
        int g = __gcd(i, y);
        if (gcds[g] == -1) gcds[g] = modpow(i, a, b);
        else if (gcds[g] != modpow(i, a, b)) {
            assert(false);
        }
    }

    cout << flush;
    int k;
    cin >> k;
    // x = 9991の時だけやばい？
    cout << gcds[k] << endl;

    int ret;
    cin >> ret;
    assert(ret == 1);
}

pii find() {
    const int MAX = 1e5+1;
    vector<int> gcds(MAX, -1);
    while (true) {
        int a = rd.get_int(100, MAX);
        int b = rd.get_int(100, MAX);

        int y = modpow(a, b, mod);
        cerr << "TEST: " << a << " " << b << endl;
        bool flg = true;
        repi(i, 100, MAX) {
            int g = __gcd(i, y);
            if (gcds[g] == -1) gcds[g] = modpow(i, a, b);
            else if (gcds[g] != modpow(i, a, b)) {
                flg = false;
                break;
            }
        }
        if (flg) return make_pair(a, b);
        rep(i, MAX) gcds[i] = -1;
    }
    // for (int b = MAX-1; b >= 100; b--) if (sieve.is_prime(b)) {
    //     int a = b-1;
    //     int y = modpow(a, b, mod);
    //     cerr << "TEST: " << b << endl;
    //     vector<set<int>> gcds(MAX);
    //     repi(i, 100, MAX) {
    //         int g = __gcd(i, y);
    //         gcds[g].insert(modpow(i, a, b));
    //         // assert(modpow(g, a, b) == modpow(i, a, b));
    //         // if (g == 1 && modpow(i, a, b) == 0) cerr << i << endl;
    //     }
    //     bool flg = true;
    //     repi(i, 1, MAX) {
    //         if ((int)gcds[i].size() > 1) {
    //             flg = false;
    //             break;
    //         }
    //     }
    //     if (flg) return b;
    // }
    return make_pair(-1, -1);
}

// int find() {
//     for (int i = 100000; i >= 100; i--) {
//         bool flg = true;
//         repi(j, 1, i) {
//             if (modpow(j, i-1, i) != 1) {
//                 flg = false;
//                 break;
//             }
//         }
//         if (i % 10000 == 0) cerr << "TEST: " << i << endl;
//         if (flg && modpow(i-1, i, mod) % i == 0) return i;
//     }
//     return -1;
// }

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    // pii p = find();
    // cout << p.first << " " << p.second << endl;
    solve();
    return 0;
}
0