結果

問題 No.551 夏休みの思い出（２）
ユーザー tsutajtsutaj
提出日時 2019-03-30 01:47:47
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,783 ms / 4,000 ms
コード長 4,451 bytes
コンパイル時間 1,380 ms
コンパイル使用メモリ 98,536 KB
実行使用メモリ 88,480 KB
最終ジャッジ日時 2024-11-07 01:50:26
合計ジャッジ時間 16,158 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 3 ms
6,816 KB
testcase_04 AC 3 ms
6,816 KB
testcase_05 AC 6 ms
6,820 KB
testcase_06 AC 7 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 3 ms
6,816 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 2 ms
6,820 KB
testcase_17 AC 4 ms
6,816 KB
testcase_18 AC 5 ms
6,820 KB
testcase_19 AC 5 ms
6,816 KB
testcase_20 AC 5 ms
6,816 KB
testcase_21 AC 5 ms
6,820 KB
testcase_22 AC 3 ms
6,820 KB
testcase_23 AC 3 ms
6,820 KB
testcase_24 AC 4 ms
6,816 KB
testcase_25 AC 4 ms
6,816 KB
testcase_26 AC 4 ms
6,820 KB
testcase_27 AC 384 ms
17,184 KB
testcase_28 AC 370 ms
16,416 KB
testcase_29 AC 80 ms
6,816 KB
testcase_30 AC 309 ms
15,136 KB
testcase_31 AC 85 ms
6,816 KB
testcase_32 AC 275 ms
14,880 KB
testcase_33 AC 383 ms
17,052 KB
testcase_34 AC 255 ms
13,472 KB
testcase_35 AC 98 ms
6,820 KB
testcase_36 AC 179 ms
10,104 KB
testcase_37 AC 1,783 ms
88,480 KB
testcase_38 AC 1,505 ms
83,000 KB
testcase_39 AC 549 ms
25,316 KB
testcase_40 AC 1,115 ms
50,812 KB
testcase_41 AC 466 ms
22,728 KB
testcase_42 AC 1,527 ms
82,952 KB
testcase_43 AC 551 ms
25,248 KB
testcase_44 AC 800 ms
42,476 KB
testcase_45 AC 594 ms
27,240 KB
testcase_46 AC 1,673 ms
82,980 KB
testcase_47 AC 2 ms
6,816 KB
testcase_48 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 離散対数問題 (Discrete Logarithm Problem) を解く
// a^x = b (mod p, p は素数) を満たすような x (1 <= x <= p-1) を求める
template <typename NumType>
struct DiscreteLogarithm {
    unordered_map<NumType, NumType> pow_table_;

    // a と p をコンストラクタで指定すると、pow_table_ が作られる
    DiscreteLogarithm() : pow_table_() {}
    DiscreteLogarithm(NumType a, NumType p, double ratio=0.5) {
        set_rec_table(a, p, ratio);
    }
    
    NumType mod_pow(NumType x, NumType k, NumType p) {
        NumType res = 1;
        for(; k>0; k>>=1) {
            if(k & 1) (res *= x) %= p;
            (x *= x) %= p;
        }
        return res;
    }

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

    // a^{-s * sqrtp} => s が格納された map を返す
    unordered_map<NumType, NumType> get_rec_table(NumType a, NumType p, double ratio=0.5) {
        unordered_map<NumType, NumType> num_rec;
        NumType sp = pow(p, ratio) + 1;
        NumType tp = pow(p, 1.0 - ratio) + 1;

        // a^{-sqrtp}
        NumType inv_pow_a = mod_inv(mod_pow(a, sp, p), p);

        // a^{-s * sqrtp}
        NumType mul = 1;
        for(NumType s=0; s<=tp; s++) {
            NumType key = mul;
            if(num_rec.count(key)) break;
            num_rec[key] = s;
            (mul *= inv_pow_a) %= p;
        }
        return num_rec;
    }

    // pow_table_ に map をセットする
    void set_rec_table(NumType a, NumType p, double ratio) {
        pow_table_ = get_rec_table(a, p, ratio);
    }

    // Baby-step Giant-step Algorithm: O(sqrt(p))
    // a^{-s * sqrtp} の map は、直前のものを使いまわすこともできる
    // pow_table_ が空の場合、または use_same_table が指定されていない場合は自動的に map が作られ、それが pow_table_ に保存される
    NumType BSGS(NumType a, NumType b, NumType p, bool use_same_table=false, double ratio=0.5) {
        a %= p, b %= p;
        NumType sp = pow(p, ratio) + 1;
        
        // a^{-s * sp} => s
        unordered_map<NumType, NumType> &num_rec = pow_table_;
        if(num_rec.empty() or !use_same_table) {
            set_rec_table(a, p, ratio);
        }
        
        // a^t * b^{-1} = a^{-s * sp}
        // この時の答えは s * sp + t
        NumType mul = mod_inv(b, p);
        for(NumType t=0; t<=sp; t++) {
            if(num_rec.count(mul)) {
                NumType s = num_rec[mul];

                // 解の範囲は 1 以上 p-1 以下なのでそれはチェックが必要
                NumType ans = s * sp + t;
                if(1 <= ans and ans <= p-1) return ans;
            }
            (mul *= a) %= p;
        }

        // 解なし
        return NumType(-1);
    }
};

// Verified on Mar 28, 2019
// Taipei Regional Contest 2015: D
// Judge: https://vjudge.net/contest/271429#problem/D
void TaipeiRegional2015_D() {
    int a, b, prime; cin >> prime;
    while(scanf("%d%d", &a, &b) == 2) {
        DiscreteLogarithm<int> dl;
        int ans = dl.BSGS(a, b, prime);
        if(ans < 0) puts("0");
        else printf("%d\n", ans);
    }
}

void yuki_551() {
    using lint = long long int;
    lint P, R, Q; cin >> P >> R >> Q;
    double ratio = 0.3;
    DiscreteLogarithm<lint> dl(R, P, ratio);
    while(Q--) {
        lint A, B, C; scanf("%lld%lld%lld", &A, &B, &C);
        lint r = dl.mod_inv(A, P);
        (A *= r) %= P;
        (B *= r) %= P;
        (C *= r) %= P;
        (B *= dl.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 が解
            lint k = dl.BSGS(R, D, P, true, ratio);
            if(k < 0 or k % 2 == 1) {
                printf("-1\n");
            }
            else {
                lint sqrtd = dl.mod_pow(R, k/2, P);
                lint X = (2*P + sqrtd - B) % P;
                lint Y = (2*P - sqrtd - B) % P;
                if(X > Y) swap(X, Y);
                printf("%lld %lld\n", X, Y);
            }
        }
    }
}

int main() {
    // TaipeiRegional2015_D();
    yuki_551();
}
0