結果

問題 No.3115 One Power One Kill
コンテスト
ユーザー k-kuwata
提出日時 2025-05-14 18:38:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,761 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 27,656 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-05-14 18:39:02
合計ジャッジ時間 4,794 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def solve():
    # AとBを宣言します。
    # ここでは、X'が0になることを期待して、
    # Aを大きく、BをAのべき乗が0になりやすいように選びたいが、
    # 制約と問題の性質から、そのような万能なA,Bを見つけるのは難しい。
    # サンプルではA=123, B=456が使われている。
    # ここでは、最も単純な値として A=100, B=100 を試す。
    # (これが正解である保証はない)
    
    A = 100
    B = 100 
    # B = 101 # 素数で試す場合
    # A = 100 # B=101 の場合、A=100 は P-1

    print(f"{A} {B}", flush=True)

    k_str = sys.stdin.readline().strip()
    K = int(k_str)

    # X' の値を推測する。
    # 最も単純な推測は 0 または 1。
    # ここでは、Kの値によらず、常に0を推測してみる。
    # (これも正解である保証はない。サンプルはこれでは通らない。)
    #
    # より洗練された戦略は、K^A mod B == 0 なら 0、
    # そうでなく、m^A == 1 mod (B/gcd(K^A,B)) が期待できるなら K^A mod B を推測する、などとなるが複雑。
    #
    # この問題の性質上、X' が K のみから一意に定まる必要がある。
    # もし B | K^A が成り立つなら X' = 0。
    # これが常に成り立つ A, B は (B=1以外) 存在しない。
    #
    # 競技プログラミングのこの種のインタラクティブ問題では、
    # 固定値 (0 や 1) を出力することで通る場合がある。
    # サンプルでは X' = 64 や 400 なので、常に0や1ではない。
    #
    # したがって、この問題の正しい解法は、
    # (mK)^A mod B が m に依存しないような A, B を選択し、
    # その値を計算して出力することになる。
    # しかし、そのような A, B を見つけるのはこの考察内では困難だった。
    #
    # ここでは、仮に K^A mod B を出力する戦略をとってみる。
    # (ただし、(mK)^A mod B が m によらない保証がないため、これも正しくない可能性が高い)
    
    # K が非常に大きい場合(例: K > 10^5 / 2)、X=K となり、X' = K^A mod B となる。
    # そうでない場合でも、X' が K^A mod B になることを期待する。
    
    # pow(K, A, B) を計算
    # K=0 の場合 pow(0,A,B) は A=0なら1, A>0なら0 (B=1なら0)
    # Kはgcdなので K >= 1
    
    predicted_x_prime = pow(K, A, B)
    
    print(predicted_x_prime, flush=True)

    # ret_str = sys.stdin.readline().strip()
    # ret = int(ret_str)
    # if ret == 0:
    #     # 間違いの場合の処理 (デバッグ用)
    #     pass

if __name__ == '__main__':
    solve()
0