結果

問題 No.551 夏休みの思い出（２）
ユーザー tottoripaper
提出日時 2017-08-08 00:26:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,165 bytes
コンパイル時間 2,478 ms
コンパイル使用メモリ 189,648 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-12-26 16:47:08
合計ジャッジ時間 38,342 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
}

// 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);
}

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

    QuadradicMod() = default;
    QuadradicMod(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 + 1) / 2);
        expos[0] = std::make_tuple(1, 0);
        {
            long long ex = 1;
            for(int i=1;i<(bucket_size + 1)/2;++i){
                ex = ex * g % p * g % p;
                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;
        }        
    }
    QuadradicMod& operator=(const QuadradicMod&) = default;
    QuadradicMod& operator=(QuadradicMod&&) = default;

    // solve g^n = b (mod p)
    long long babyStepGiantStep(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
    }

    long long modSqrt(long long x){
        if(x % p == 0){return 0ll;}
        
        long long gcd, s;
        std::tie(gcd, s, std::ignore) = extgcd(2ll, p-1);

        long long m = babyStepGiantStep(x);
            
        if(m == -1){
            return -1;
        }

        long long  t = s * (m / gcd) % (p - 1);
        t = t >= 0 ? t : t + (p - 1);
            
        return expt(g, t, p);
    }

    // solve ax^2 + bx + c \equiv 0 (mod p)
    std::tuple<long long, long long> solve(long long a, long long b, long long c){
        long long D = (b * b - 4ll * a * c) % p;
        D = D >= 0 ? D : D + p;
        long long sq = modSqrt(D);

        if(sq == -1){return std::make_tuple(-1, -1);}
        
        long long den = inverse(2ll * a % p, p);
        
        long long 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);}

        return std::make_tuple(x0, x1);
    }
};

QuadradicMod quadradicMod;

int ti;
ll P, R;

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

    ti = 12;

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

    quadradicMod = std::move(QuadradicMod(P, R, (int)std::sqrt(P) * ti));
    
    int Q;
    scanf("%d", &Q);
        
    for(int i=0;i<Q;++i){
        ll a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);

        ll x0, x1;
        tie(x0, x1) = quadradicMod.solve(a, b, c);

        if(x0 == -1){puts("-1"); continue;}
        
        if(x0 == x1){
            printf("%lld\n", x0);
        }else{
            printf("%lld %lld\n", x0, x1);
        }
    }
}
0