結果

問題 No.551 夏休みの思い出（２）
ユーザー PachicobuePachicobue
提出日時 2017-07-29 00:19:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,816 bytes
コンパイル時間 1,801 ms
コンパイル使用メモリ 177,956 KB
実行使用メモリ 7,800 KB
最終ジャッジ日時 2024-10-10 11:01:01
合計ジャッジ時間 8,092 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#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;
        if (B == 0 and C == 0) {
            cout << 0 << endl;
            continue;
        }
        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