結果

問題 No.551 夏休みの思い出（２）
ユーザー tottoripapertottoripaper
提出日時 2017-08-08 00:08:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,785 bytes
コンパイル時間 2,331 ms
コンパイル使用メモリ 187,820 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-10-11 22:39:23
合計ジャッジ時間 29,139 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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 ModSqrt{
    int bucket_size, bucket_n;
    long long p, g;    
    std::vector<std::tuple<long long, long long>> expos;
    std::vector<long long> invs;

    ModSqrt() = default;
    ModSqrt(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;
        }        
    }
    ModSqrt& operator=(const ModSqrt&) = default;
    ModSqrt& operator=(ModSqrt&&) = 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 g, s;
        std::tie(g, s, std::ignore) = extgcd(2ll, p-1);

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

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



ModSqrt modSqrt;

int ti;
ll P, R;

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

    ti = 12;

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

    modSqrt = std::move(ModSqrt(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 D = (b * b - 4ll * a * c) % P;
        D = D >= 0 ? D : D + P;
        
        ll sq = modSqrt.modSqrt(D);
        if(sq == -1){puts("-1"); continue;}
        
        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