結果

問題 No.3115 One Power One Kill
コンテスト
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 14:06:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,223 bytes
コンパイル時間 623 ms
コンパイル使用メモリ 69,792 KB
実行使用メモリ 26,224 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-04-19 14:06:14
合計ジャッジ時間 4,170 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>   // 虽然最终逻辑没用到，但包含进来是好习惯
#include <numeric>  // 虽然最终逻辑没用到，但包含进来是好习惯
#include <utility>  // 如果使用迭代式 gcd 会用到 std::swap

int main() {
    // 选择 A = p-1 和 B = p，其中 p 是一个介于 100 和 10^5 之间的素数。
    // 我们选择 p = 101，这是 >= 100 的最小素数。
    long long a = 100; // A = p - 1
    long long b = 101; // B = p (素数)

    // 检查约束条件: 100 <= A <= 10^5 且 100 <= B <= 10^5
    // 我们的选择满足这些条件。

    // 输出 A 和 B，并刷新输出缓冲区。
    // 必须刷新以确保评测系统能接收到输出。
    std::cout << a << " " << b << std::endl;

    // 从评测系统读取 K (gcd 值)。
    long long k;
    if (!(std::cin >> k)) {
        // 处理潜在的输入错误
        return 1;
    }

    // 核心逻辑依赖于费马小定理。
    // X' = X_new^A mod B = X_new^(p-1) mod p.
    // 我们证明了 Y = A^B mod (10^9+7) 不能被 B=p 整除。
    // 因此，gcd(X_new, Y) = K 能被 p 整除 当且仅当 X_new 能被 p 整除。
    //
    // 情况 1: K 能被 B (p) 整除。
    // 这意味着 X_new 必须能被 p 整除。
    // 那么 X' = X_new^(p-1) mod p = 0^(p-1) mod p = 0 (因为 p-1 >= 1)。
    //
    // 情况 2: K 不能被 B (p) 整除。
    // 这意味着 X_new 不能被 p 整除。
    // 根据费马小定理, X_new^(p-1) ≡ 1 (mod p)。
    // 那么 X' = 1.

    long long predicted_x_prime;
    if (k % b == 0) {
        // 如果 K 能被 p 整除，预测 X' = 0
        predicted_x_prime = 0;
    } else {
        // 如果 K 不能被 p 整除，预测 X' = 1
        predicted_x_prime = 1;
    }

    // 输出预测的 X' 值，并刷新输出缓冲区。
    std::cout << predicted_x_prime << std::endl;

    // 从评测系统读取最终结果 (ret=1 表示正确, ret=0 表示错误)。
    // 这主要用于测试或提交后验证。
    int ret;
     if (!(std::cin >> ret)) {
         // 处理潜在的输入错误
         return 1;
     }
    // 程序本身的逻辑不需要使用 'ret'。

    return 0; // 表示成功执行。
}
0