結果

問題 No.3115 One Power One Kill
コンテスト
ユーザー karashi-0086A2
提出日時 2025-04-20 16:10:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,314 bytes
コンパイル時間 2,266 ms
コンパイル使用メモリ 194,968 KB
実行使用メモリ 26,480 KB
平均クエリ数 1.00
最終ジャッジ日時 2025-04-20 16:10:18
合計ジャッジ時間 7,051 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const ll MOD = 1e9 + 7;

// 繰り返し二乗法 (a^b % mod)
ll modpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    // 戦略的に A と B を選ぶ（固定でも OK）
    ll A = 101 * 103 * 107;  // 小さい素数の積
    ll B = 100003;           // 大きめの素数

    // Y = A^B mod MOD を求める
    ll Y = modpow(A, B, MOD);

    // A と B を出力（ジャッジに送信）
    cout << A << " " << B << endl;
    cout.flush();

    // ジャッジから GCD(X, Y) = K を受け取る
    ll K;
    cin >> K;

    // X の候補を全探索（X ∈ [100, 100000]）
    vector<ll> candidates;
    for (ll x = 100; x <= 100000; ++x) {
        if (__gcd(x, Y) == K) {
            candidates.push_back(x);
        }
    }

    // X′ = X^A mod B を計算して候補から1つ選ぶ（今回は最初の候補）
    if (candidates.empty()) {
        cerr << "No valid X found." << endl;
        return 1;
    }

    ll x = candidates[0];
    ll X_prime = modpow(x, A, B);

    // 推測した X′ を出力
    cout << X_prime << endl;
    cout.flush();

    return 0;
}
0