結果

問題 No.551 夏休みの思い出（２）
コンテスト
ユーザー Pachicobue
提出日時 2017-07-29 00:16:26
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 3,720 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,900 ms
コンパイル使用メモリ 178,248 KB
実行使用メモリ 9,268 KB
最終ジャッジ日時 2024-10-10 07:08:28
合計ジャッジ時間 8,354 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31 RE * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz=" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = 1e9 + 7;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

ll P, R;

ll power(ll p, ll n)
{
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        const ll q = power(p, n / 2);
        return (q * q) % P;
    } else {
        return (p * power(p, n - 1)) % P;
    }
}

template <typename T>
pair<T, T> extgcd(const T x, const T y)
// x,y>0 & relatively prime
// returns (a,b) s.t. ax+by=1
{
    ll r0 = x;
    ll r1 = y;
    ll a0 = 1;
    ll a1 = 0;
    ll b0 = 0;
    ll b1 = 1;
    while (r1 > 0) {
        const ll q1 = r0 / r1;
        const ll r2 = r0 % r1;
        const ll a2 = a0 - q1 * a1;
        const ll b2 = b0 - q1 * b1;
        r0 = r1;
        r1 = r2;
        a0 = a1;
        a1 = a2;
        b0 = b1;
        b1 = b2;
    }
    return make_pair(a0 / r0, b0 / r0);
}

bool quadratic(ll a)
{
    if (a == 0) {
        return true;
    }
    return power(a, (P - 1) / 2) == 1;
}

ll divide(ll a, ll b, ll mod = P)  // b/a
{
    const ll x = (((extgcd(a, mod).first + mod) % mod) * b) % mod;
    assert((a * x) % mod == b);
    return x;
}

template <typename T>
T gcd(const T a, const T b)
{
    return b ? gcd(b, a % b) : a;
}

mt19937 mt{random_device{}()};
ll rho(ll a)
{
    const ll mod = P - 1;
    static uniform_int_distribution<ll> dist{0, P - 2};
    unordered_map<ll, pair<ll, ll>> mp;
    while (true) {
        const ll alpha = dist(mt);
        const ll beta = dist(mt);
        const ll c = (power(a, alpha) * power(R, beta)) % P;
        if (mp.find(c) != mp.end()) {
            const auto& p = mp[c];
            const ll alpha_ = p.first;
            const ll beta_ = p.second;
            if (alpha == alpha_) {
                continue;
            }
            const ll a_ = (((alpha_ - alpha) % mod) + mod) % mod;
            const ll b_ = (((beta - beta_) % mod) + mod) % mod;
            const ll g = gcd(a_, b_);
            const ll x = divide(a_ / g, b_ / g, mod);
            if (power(R, x) == a) {
                return x;
            }
        }
        mp[c] = make_pair(alpha, beta);
    }
}
ll square_root(ll n)
{
    if (n == 0) {
        return 0;
    }
    if (P % 4 == 3) {
        return power(n, (P + 1) / 4);
    }
    const ll a = rho(n);
    const ll ind = (a % 2 == 0) ? a / 2 : (a + P) / 2;
    return power(R, ind);
}

int main()
{
    cin >> P >> R;

    ll Q;
    cin >> Q;
    for (ll q = 0; q < Q; q++) {
        ll A, B, C;
        cin >> A >> B >> C;
        const ll elem = (((B * B) % P - (4 * A * C) % P) % P + P) % P;
        if (not quadratic(elem)) {
            cout << -1 << endl;
            continue;
        }
        const ll root = square_root(elem);
        const ll mini = ((-root - B) % P + P) % P;
        const ll maxi = ((root - B) % P + P) % P;

        const ll g1 = gcd(2 * A, mini);
        const ll g2 = gcd(2 * A, maxi);
        const ll ans1 = divide(2 * A / g1, mini / g1);
        const ll ans2 = divide(2 * A / g2, maxi / g2);
        if (ans1 == ans2) {
            cout << ans1 << endl;
        } else {
            cout << min(ans1, ans2) << " " << max(ans1, ans2) << endl;
        }
    }
    return 0;
}
0