結果

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

ソースコード

diff # 

import sys

def solve():
    """
    Solves the interactive problem.
    The strategy is to choose A and B such that the final value X' = X^A mod B
    can be uniquely determined from the revealed value K = gcd(X, Y).

    We choose A = 100 and B = 101.
    B = 101 is a prime number.
    A = 100 = B - 1.

    The value we need to predict is X'_final = X_new^A mod B, where X_new is
    chosen by the judge from the set S'(K) = {x | 100 <= x <= 10^5, gcd(x, Y) = K},
    and Y = A^B mod (10^9 + 7).
    Our prediction must be correct for any X_new the judge might choose. This means
    X_new^A mod B must be constant for all X_new in S'(K).

    Let's analyze X' = X^A mod B = X^100 mod 101.
    Since B=101 is prime, by Fermat's Little Theorem:
    - If X is divisible by 101 (X % 101 == 0), then X^100 === 0^100 === 0 (mod 101).
    - If X is not divisible by 101 (X % 101 != 0), then X^(101-1) = X^100 === 1 (mod 101).
    So, X' depends only on whether X is divisible by 101.

    Now we need to show that for any given K, all X_new in S'(K) have the same
    divisibility by 101. This divisibility must be determined by K.

    Let p = 101. K = gcd(X_new, Y).

    Case 1: K is divisible by p (K % 101 == 0).
      Since K divides X_new (because K = gcd(X_new, Y)), X_new must also be divisible by p.
      Therefore, all X_new in S'(K) are divisible by 101.
      The required value X' = X_new^100 mod 101 is 0 for all such X_new.
      The correct output is 0.

    Case 2: K is not divisible by p (K % 101 != 0).
      We need to show that X_new cannot be divisible by p.
      Assume, for contradiction, that X_new is divisible by p (X_new = p * m for some integer m).
      Then K = gcd(X_new, Y) = gcd(p * m, Y).
      If Y is also divisible by p (Y = p * n), then K = gcd(p*m, p*n) = p * gcd(m, n). In this case, K would be divisible by p, which contradicts our assumption that K is not divisible by p.
      If Y is not divisible by p (gcd(p, Y) = 1), then K = gcd(p*m, Y) = gcd(m, Y) (since p is prime and does not divide Y). In this case, K = gcd(m, Y). Since p does not divide Y, p also does not divide gcd(m, Y) = K. So, if Y is not divisible by p, and X_new is divisible by p, then K is not divisible by p.
      However, if X_new is divisible by p, K = gcd(X_new, Y) could potentially depend on Y's divisibility by p.
      Let's analyze directly: K is not divisible by p. If X_new were divisible by p, then p would be a common divisor of X_new and potentially Y. But if p divides K, K would be divisible by p. Since K is not divisible by p, p cannot be a common divisor that contributes to K. This means p cannot divide X_new?
      Let's be precise: K = gcd(X_new, Y). p does not divide K.
      If X_new were divisible by p, then any common divisor of X_new and Y cannot be a multiple of p (otherwise K would be a multiple of p).
      Assume X_new is divisible by p. Let X_new = p*m.
          If Y is divisible by p, Y = p*n. K = gcd(p*m, p*n) = p*gcd(m,n). K is divisible by p. Contradiction.
          If Y is not divisible by p. K = gcd(p*m, Y) = gcd(m, Y) (since gcd(p,Y)=1). K = gcd(m,Y). Is K divisible by p? No, because p does not divide Y.
      So, if K is not divisible by p, X_new *must* not be divisible by p.
      Therefore, all X_new in S'(K) are not divisible by 101.
      The required value X' = X_new^100 mod 101 is 1 for all such X_new.
      The correct output is 1.

    The logic holds regardless of the properties of Y.
    The strategy is: choose A=100, B=101. Read K. If K is divisible by 101, output 0. Otherwise, output 1.
    """

    # Choose A and B according to the strategy.
    a = 100
    b = 101

    # Output A and B to the judge.
    print(f"{a} {b}", flush=True)

    # Read the value K provided by the judge.
    k = int(sys.stdin.readline())

    # Determine the output based on the divisibility of K by 101.
    if k % 101 == 0:
        print(0, flush=True)
    else:
        print(1, flush=True)

# Execute the solving function.
solve()
0