結果

問題 No.551 夏休みの思い出（２）
ユーザー tsutajtsutaj
提出日時 2019-04-09 17:11:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 70 ms / 4,000 ms
コード長 3,320 bytes
コンパイル時間 1,054 ms
コンパイル使用メモリ 89,904 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 02:41:11
合計ジャッジ時間 4,329 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 7 ms
6,940 KB
testcase_04 AC 10 ms
6,940 KB
testcase_05 AC 20 ms
6,940 KB
testcase_06 AC 28 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 3 ms
6,940 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 64 ms
6,944 KB
testcase_28 AC 63 ms
6,940 KB
testcase_29 AC 58 ms
6,944 KB
testcase_30 AC 62 ms
6,940 KB
testcase_31 AC 58 ms
6,944 KB
testcase_32 AC 60 ms
6,940 KB
testcase_33 AC 63 ms
6,944 KB
testcase_34 AC 64 ms
6,944 KB
testcase_35 AC 62 ms
6,940 KB
testcase_36 AC 64 ms
6,940 KB
testcase_37 AC 69 ms
6,940 KB
testcase_38 AC 68 ms
6,940 KB
testcase_39 AC 67 ms
6,944 KB
testcase_40 AC 68 ms
6,944 KB
testcase_41 AC 64 ms
6,944 KB
testcase_42 AC 68 ms
6,940 KB
testcase_43 AC 68 ms
6,944 KB
testcase_44 AC 68 ms
6,944 KB
testcase_45 AC 66 ms
6,944 KB
testcase_46 AC 70 ms
6,940 KB
testcase_47 AC 2 ms
6,944 KB
testcase_48 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <random>
using namespace std;

// Tonelli-Shanks Algorithm
// 素数 p を法とし、n が与えられたとき、
// r^2 = n (mod p) を満たす r を求める

struct QuadraticResidue {
    using lint = long long int;
    QuadraticResidue() {}

    // x^k (mod p)
    lint mod_pow(lint x, lint k, lint p) {
        lint res = 1;
        for(; k>0; k>>=1) {
            if(k & 1) (res *= x) %= p;
            (x *= x) %= p;
        }
        return res;
    }

    lint mod_inv(lint x, lint p) {
        return mod_pow(x, p-2, p);
    }

    // ルジャンドル記号 (a/p) = a^{\frac{p-1}{2}} (p が奇素数の場合)
    // (a/p) =  0 ... a = 0 (mod p)
    // (a/p) =  1 ... a が p を法として平方剰余
    // (a/p) = -1 ... a が p を法として平方剰余でない
    // 平方根の解の存在がこれで確認できる
    lint Legendre(lint a, lint p) {
        if(a % p == 0) return 0;
        lint res = mod_pow(a, (p-1)/2, p);
        if(res == p-1) return -1;
        return res;
    }

    // r^2 = n (mod p) なる r を求める
    vector<lint> TonelliShanks(lint n, lint p) {
        if(Legendre(n, p) == -1) return {};

        lint Q = p - 1, S = 0;
        while(Q % 2 == 0) Q /= 2, S++;

        random_device seed_gen;
        mt19937_64 mt(seed_gen());
        uniform_int_distribution<lint> dist(0, p-1);
        lint z = dist(mt);
        while(Legendre(z, p) != -1) z = dist(mt);

        lint M = S;
        lint c = mod_pow(z, Q, p);
        lint t = mod_pow(n, Q, p);
        lint R = mod_pow(n, (Q+1)/2, p);

        lint r = -1;
        while(1) {
            if(t == 0) { r = 0; break; }
            if(t == 1) { r = R; break; }

            lint i = 1, tt = t * t % p;
            for(i=1; i<M; i++) {
                if(tt == 1) break;
                tt = tt * tt % p;
            }
            if(i == M) return {};

            lint b = c;
            for(lint j=0; j<M-i-1; j++) {
                b = b * b % p;
            }
            
            M = i;
            c = b * b % p;
            t = t * c % p;
            R = R * b % p;
        }

        vector<lint> ans;
        ans.push_back(r);
        if(r != p - r) ans.push_back(p - r);
        return ans;
    }
};

void yuki_551() {
    using lint = long long int;
    lint P, R, Q; cin >> P >> R >> Q;
    QuadraticResidue qr;
    while(Q--) {
        lint A, B, C; scanf("%lld%lld%lld", &A, &B, &C);
        lint r = qr.mod_inv(A, P);
        (A *= r) %= P;
        (B *= r) %= P;
        (C *= r) %= P;
        (B *= qr.mod_inv(2, P)) %= P;

        lint D = (P - C + (B*B%P)) % P;
        if(D == 0) {
            printf("%lld\n", (P - B) % P);
        }
        else {
            // R^k = D なる D を求める
            // k が奇数 ... 解なし
            // k が偶数 ... k/2 と k/2 + (P-1)/2 が解
            vector<lint> ks = qr.TonelliShanks(D, P);
            if(ks.size() == 0) {
                printf("-1\n");
            }
            else {
                lint X = (2*P + ks[0] - B) % P;
                lint Y = (2*P + ks[1] - B) % P;
                if(X > Y) swap(X, Y);
                printf("%lld %lld\n", X, Y);
            }
        }
    }
}

int main() {
    yuki_551();
}
0