結果
| 問題 | No.551 夏休みの思い出（２） |
| ユーザー |
 minami
|
| 提出日時 | 2019-04-01 15:19:26 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,414 bytes |
| コンパイル時間 | 1,667 ms |
| コンパイル使用メモリ | 169,276 KB |
| 実行使用メモリ | 13,888 KB |
| 最終ジャッジ日時 | 2024-05-03 22:29:29 |
| 合計ジャッジ時間 | 8,369 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
ソースコード
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif
#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }
// 累乗
// O(log e)
// mod^2 が long long の最大値より大きければオーバーフローするので掛け算に modmul を使う
long long modpow(long long a, long long e, long long mod) {
long long res = 1;
while (e > 0) {
if (e & 1)res = res * a % mod; // modmul(res, a, mod);
a = a * a % mod; // modmul(a, a, mod);
e >>= 1;
}
return res;
}
// 逆元
// O(log mod)
long long modinv(long long a, long long mod) {
return modpow(a, mod - 2, mod);
}
// Legendre symbol
// a|p なら 0
// a が平方剰余なら 1
// a が平方非剰余なら -1
int legendre(long long a, long long p) {
long long l = modpow(a, (p - 1) / 2, p);
return l == p - 1 ? -1 : l;
}
long long modsqrt(long long a, long long p) {
int l = legendre(a, p);
if (l != 1)return l;
long long S = 0, Q = p - 1;
while (!(Q & 1)) {
S++;
Q >>= 1;
}
long long z = 1;
while (legendre(z, p) == 1)z++;
long long M = S;
long long c = modpow(z, Q, p);
long long t = modpow(a, Q, p);
long long R = modpow(a, (Q + 1) / 2, p);
while (t != 1) {
for (int i = 1; i < M; i++) {
if (modpow(t, 1 << i, p) != 1)continue;
long long b = modpow(c, 1 << (M - i - 1), p);
c = b * b % p;
t = t * b % p * b % p;
R = R * b % p;
break;
}
}
return R;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int P = 17;
rep(a, 0, P) {
legendre(a, P);
}
int p, r, q; cin >> p >> r >> q;
rep(_, 0, q) {
int a, b, c; cin >> a >> b >> c;
int ainv = modinv(a, p);
int A = ((b*b%p*modinv(4, p) % p*ainv%p*ainv%p + p - c) % p)*ainv%p;
int X = modsqrt(A, p);
if (X <= 0) {
cout << X << endl;
}
else {
int Y = p - X;
int x = (X + p - b * modinv(2, p) % p * ainv) % p;
int y = (Y + p - b * modinv(2, p) % p * ainv) % p;
if (x > y)swap(x, y);
cout << x << " " << y << endl;
}
}
return 0;
}