結果

問題 No.551 夏休みの思い出（２）
コンテスト
ユーザー tottoripaper
提出日時 2017-08-07 23:56:07
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3,502 ms / 4,000 ms
コード長 4,037 bytes
記録
コンパイル時間 2,058 ms
コンパイル使用メモリ 189,172 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-10-11 23:39:28
合計ジャッジ時間 29,510 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)

using ll = long long;

template <typename T>
T expt(T a, T n, T mod = std::numeric_limits<T>::max()){
    T res = 1;
    while(n){
        if(n & 1){res = res * a % mod;}
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

template <typename T>
T inverse(T n, T mod){
    return expt(n, mod-2, mod);
}

struct BabyStepGiantStep{
    int bucket_size, bucket_n;
    long long p, g;    
    std::vector<std::tuple<long long, long long>> expos;
    std::vector<long long> invs;

    BabyStepGiantStep() = default;
    BabyStepGiantStep(long long p, long long g, int bucket_size) : p(p), g(g), bucket_size(bucket_size) {
        bucket_n = (p + bucket_size - 1) / bucket_size;
        // expos = std::vector<std::tuple<long long, long long>>(bucket_size);
        expos = std::vector<std::tuple<long long, long long>>((bucket_size + 1) / 2);
        expos[0] = std::make_tuple(1, 0);
        {
            long long ex = 1;
            // for(int i=1;i<bucket_size;++i){
            for(int i=1;i<(bucket_size + 1)/2;++i){
                // ex = ex * g % p;
                ex = ex * g % p * g % p;
                // expos[i] = std::make_tuple(ex, i);
                expos[i] = std::make_tuple(ex, i * 2);
            }
        }
        std::sort(expos.begin(), expos.end());

        invs = std::vector<long long>(bucket_n);
        
        long long alpha = expt<long long>(g, bucket_size, p),
            inv_alpha = inverse(alpha, p);

        invs[0] = 1ll;
        for(int i=0;i+1<bucket_n;++i){
            invs[i+1] = invs[i] * inv_alpha % p;
        }        
    }
    BabyStepGiantStep& operator=(const BabyStepGiantStep&) = default;
    BabyStepGiantStep& operator=(BabyStepGiantStep&&) = default;

    // solve g^n = b (mod p)
    long long solve(long long b){
        for(long long i=0;i<bucket_n;++i){
            long long v = b * invs[i] % p;
        
            auto it = std::lower_bound(expos.begin(), expos.end(), std::make_tuple(v, 0), [](const auto& lhs, const auto& rhs){return std::get<0>(lhs) < std::get<0>(rhs);});
        
            if(it != expos.end() && std::get<0>(*it) == v){
                long long c = i * bucket_size + std::get<1>(*it);
                return c;
            }
        }

        return -1; // no solution
    }
};

// extgcd(a, b) = (g, s, t)
// g: GCD of a and b, s, t: a solution of sa + tb = g
template <typename T>
std::tuple<T, T, T> extgcd(T a, T b){
    if(b == 0){
        return std::make_tuple(a, 1, 0);
    }
    T g, _s, _t;
    std::tie(g, _s, _t) = extgcd(b, a % b);
    return std::make_tuple(g, _t, _s - (a/b) * _t);
}

BabyStepGiantStep babyStepGiantStep;

int ti;
ll P, R;

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    ti = 12;

    scanf("%lld %lld", &P, &R);

    babyStepGiantStep = std::move(BabyStepGiantStep(P, R, (int)std::sqrt(P) * ti));
    
    ll g, s;
    tie(g, s, ignore) = extgcd(2ll, P-1);
    
    int Q;
    scanf("%d", &Q);
        
    for(int i=0;i<Q;++i){
        ll a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);

        ll D = (b * b - 4ll * a * c) % P;
        D = D >= 0 ? D : D + P;
        
        ll sq;

        if(D == 0){
            sq = 0;
        }else{
            ll m = babyStepGiantStep.solve(D);
            
            if(m == -1){
                puts("-1");
                continue;
            }
            
            ll t = s * (m / g) % (P - 1);
            t = t >= 0 ? t : t + (P - 1);
            
            sq = expt(R, t, P);
        }

        ll den = inverse(2ll * a % P, P);
        
        ll x0 = (-b - sq) * den % P,
            x1 = (-b + sq) * den % P;
        x0 = x0 >= 0 ? x0 : x0 + P;
        x1 = x1 >= 0 ? x1 : x1 + P;

        if(x0 > x1){swap(x0, x1);}
        if(x0 == x1){
            printf("%lld\n", x0);
        }else{
            printf("%lld %lld\n", x0, x1);
        }
    }
}
0