結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | tsutaj |
提出日時 | 2019-04-09 17:20:05 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 52 ms / 4,000 ms |
コード長 | 3,384 bytes |
コンパイル時間 | 880 ms |
コンパイル使用メモリ | 89,172 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 02:50:30 |
合計ジャッジ時間 | 2,930 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 3 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 6 ms
6,944 KB |
testcase_06 | AC | 7 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 1 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,944 KB |
testcase_27 | AC | 34 ms
6,940 KB |
testcase_28 | AC | 32 ms
6,940 KB |
testcase_29 | AC | 27 ms
6,944 KB |
testcase_30 | AC | 42 ms
6,944 KB |
testcase_31 | AC | 27 ms
6,944 KB |
testcase_32 | AC | 38 ms
6,940 KB |
testcase_33 | AC | 33 ms
6,944 KB |
testcase_34 | AC | 30 ms
6,944 KB |
testcase_35 | AC | 30 ms
6,940 KB |
testcase_36 | AC | 32 ms
6,940 KB |
testcase_37 | AC | 36 ms
6,944 KB |
testcase_38 | AC | 37 ms
6,944 KB |
testcase_39 | AC | 36 ms
6,944 KB |
testcase_40 | AC | 37 ms
6,944 KB |
testcase_41 | AC | 52 ms
6,940 KB |
testcase_42 | AC | 35 ms
6,940 KB |
testcase_43 | AC | 33 ms
6,944 KB |
testcase_44 | AC | 32 ms
6,944 KB |
testcase_45 | AC | 32 ms
6,944 KB |
testcase_46 | AC | 34 ms
6,940 KB |
testcase_47 | AC | 2 ms
6,940 KB |
testcase_48 | AC | 2 ms
6,940 KB |
ソースコード
#include <cstdio>#include <vector>#include <iostream>#include <algorithm>#include <random>using namespace std;// Tonelli-Shanks Algorithm// 素数 p を法とし、n が与えられたとき、// r^2 = n (mod p) を満たす r を求めるstruct QuadraticResidue {using lint = long long int;QuadraticResidue() {}// x^k (mod p)lint mod_pow(lint x, lint k, lint p) {lint res = 1;for(; k>0; k>>=1) {if(k & 1) (res *= x) %= p;(x *= x) %= p;}return res;}lint mod_inv(lint x, lint p) {return mod_pow(x, p-2, p);}// ルジャンドル記号 (a/p) = a^{\frac{p-1}{2}} (p が奇素数の場合)// (a/p) = 0 ... a = 0 (mod p)// (a/p) = 1 ... a が p を法として平方剰余// (a/p) = -1 ... a が p を法として平方剰余でない// 平方根の解の存在がこれで確認できるlint Legendre(lint a, lint p) {if(a % p == 0) return 0;lint res = mod_pow(a, (p-1)/2, p);if(res == p-1) return -1;return res;}// r^2 = n (mod p) なる r を求める (mod p 上での n の平方根)vector<lint> TonelliShanks(lint n, lint p) {if(Legendre(n, p) == -1) return {};if(p == 2) {if(n == 0) return {0};if(n == 1) return {1};}lint Q = p - 1, S = 0;while(Q % 2 == 0) Q /= 2, S++;lint z = 2;while(z < p and Legendre(z, p) != -1) z++;if(z == p) return {};lint M = S;lint c = mod_pow(z, Q, p);lint t = mod_pow(n, Q, p);lint R = mod_pow(n, (Q+1)/2, p);lint r = -1;while(1) {if(t == 0) { r = 0; break; }if(t == 1) { r = R; break; }lint i = 1, tt = t * t % p;for(i=1; i<M; i++) {if(tt == 1) break;tt = tt * tt % p;}if(i == M) return {};lint b = c;for(lint j=0; j<M-i-1; j++) {b = b * b % p;}M = i;c = b * b % p;t = t * c % p;R = R * b % p;}vector<lint> ans;ans.push_back(r);if(r != p - r) ans.push_back(p - r);return ans;}};// Verified on Apr 09, 2019// yukicoder No.551: 夏休みの思い出 (2)// Judge: https://yukicoder.me/problems/no/551void yuki_551() {using lint = long long int;lint P, R, Q; cin >> P >> R >> Q;QuadraticResidue qr;while(Q--) {lint A, B, C; scanf("%lld%lld%lld", &A, &B, &C);lint r = qr.mod_inv(A, P);(A *= r) %= P;(B *= r) %= P;(C *= r) %= P;(B *= qr.mod_inv(2, P)) %= P;lint D = (P - C + (B*B%P)) % P;if(D == 0) {printf("%lld\n", (P - B) % P);}else {// D の平方根を求めるvector<lint> ks = qr.TonelliShanks(D, P);if(ks.size() == 0) {printf("-1\n");}else {lint X = (2*P + ks[0] - B) % P;lint Y = (2*P + ks[1] - B) % P;if(X > Y) swap(X, Y);printf("%lld %lld\n", X, Y);}}}}int main() {yuki_551();}