結果

問題 No.3115 One Power One Kill
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-08-26 03:19:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,512 bytes
コンパイル時間 2,967 ms
コンパイル使用メモリ 277,616 KB
実行使用メモリ 26,252 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-08-26 03:19:31
合計ジャッジ時間 6,157 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       Bを素数とする。
       また、AをB-1の倍数とすると、
       XがBの倍数でないとき、フェルマーの小定理より、
       X^A mod B = 0

       KからXがBの倍数かどうか知るには？
       YがBの倍数であるならば、
       K = gcd(X, Y)がBの倍数であるならば、XはBの倍数であることがわかり
       KがBの倍数でないならば、XはBの倍数でない。
       よって、YがBの倍数であるような、A, Bのペアを見つければ良い。
    */

    /*
    int N=100000;
    vector<bool> prime(N+1, 1);
    for (int i=2; i<=N; i++){
        if (prime[i]){
            for (int j=i*2; j<=N; j+=i) prime[j] = 0;
        }
    }
    vector<int> v;
    for (int i=100; i<=N; i++) if (prime[i]) v.push_back(i);
    for (auto b : v){
        for (int a=b-1; a<=N; a+=(b-1)){
            ll Y = mint(a).pow(b).val();
            if (Y % b == 0){
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }
    */
    ll A=19000, B=101, Y=mint(A).pow(B).val();
    cout << A << " " << B << endl;
    ll K;
    cin >> K;
    if (K % B == 0) cout << 0 << endl;
    else cout << 1 << endl;
    ll v;
    cin >> v;
    assert(v == 1);

    return 0;
}
0