結果
| 問題 | No.551 夏休みの思い出（２） |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2017-07-29 01:30:43 |
| 言語 | Java (openjdk 23) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,925 bytes |
| コンパイル時間 | 2,601 ms |
| コンパイル使用メモリ | 83,168 KB |
| 実行使用メモリ | 57,668 KB |
| 最終ジャッジ日時 | 2024-10-10 18:39:56 |
| 合計ジャッジ時間 | 8,571 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 17 RE * 30 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
new Main().run();
}
static long time = 0;
public void run() {
Scanner sc = new Scanner();
int P = sc.nextInt();
int R = sc.nextInt();
int N = sc.nextInt();
long[] A = new long[N];
long[] B = new long[N];
long[] C = new long[N];
PrintWriter pw = new PrintWriter(System.out);
long inv2 = inv(2, P);
for (int i = 0; i < N; ++i) {
A[i] = sc.nextInt();
B[i] = sc.nextInt();
C[i] = sc.nextInt();
long invA = inv(A[i], P);
B[i] = invA * B[i] % P;
C[i] = invA * C[i] % P;
A[i] = 1;
long v = B[i] * B[i] - 4 * C[i];
v %= P;
while (v < 0)
v += P;
if (v == 0 || pow(v, (P - 1) / 2, P) == 1) {
v = calc(v, P);
long[] ans = { inv2 * (-B[i] + v), inv2 * (-B[i] + P - v) };
for (int j = 0; j < ans.length; ++j) {
ans[j] %= P;
while (ans[j] < 0)
ans[j] += P;
}
if (ans[0] > ans[1]) {
long tmp = ans[0];
ans[0] = ans[1];
ans[1] = tmp;
}
if (ans[0] == ans[1]) {
pw.println(ans[0]);
} else {
pw.println(ans[0] + " " + ans[1]);
}
} else {
pw.println(-1);
}
}
pw.close();
}
// x^2=aとなるxを探す
static long calc(long a, long mod) {
for (int b = 0; b < 100; ++b) {
Poly p1 = new Poly(mod);
Poly p2 = new Poly(mod);// (x-b)^2-a=0 mod p
p2.add(2, 1);
p2.add(1, -2 * b);
p2.add(0, b * b - a);
p1.add(1, 1);
p1 = p1.pow((mod - 1) / 2, p2);
p1.add(0, -1);
Poly gcd = p1.gcd(p2);
if (gcd.deg() == 1) {
long ans = (-b - inv(gcd.val[1], mod) * gcd.val[0]) % mod;
while (ans < 0)
ans += mod;
return ans;
}
}
throw new AssertionError();
}
static class Poly {
long[] val = new long[3];
long mod;
public Poly(long mod) {
this.mod = mod;
}
void add(int deg, long v) {
val[deg] += v;
while (val[deg] < 0)
val[deg] += mod;
val[deg] %= mod;
}
int deg() {
int deg = val.length - 1;
while (deg > 0 && val[deg] == 0)
--deg;
return deg;
}
void mul(Poly p) {
val[2] = val[1] * p.val[1];
val[1] = val[0] * p.val[1] + val[1] * p.val[1];
val[0] = val[0] * val[0];
for (int i = 0; i < val.length; ++i) {
val[i] %= mod;
}
}
Poly mod(Poly p) {
Poly ret = new Poly(mod);
Poly modPoly = new Poly(mod);
for (int i = 0; i < val.length; ++i) {
ret.add(i, val[i]);
}
int max = p.deg();
if (max == 0 && p.val[max] == 0)
return new Poly(mod);
long rev = (long) inv(p.val[max], mod);
for (int i = 0; i < p.val.length; ++i) {
modPoly.add(i, p.val[i] * rev);
}
for (int i = ret.val.length - 1; i >= max; --i) {
if (ret.val[i] == 0)
continue;
long tmp = ret.val[i];
for (int j = 0; j <= max; ++j) {
ret.add(i - j, -tmp % mod * modPoly.val[max - j] % mod);
}
}
return ret;
}
Poly gcd(Poly p) {
int deg1 = this.deg();
int deg2 = p.deg();
if (deg1 > deg2) {
return p.gcd(this);
}
if (deg1 == 0 && val[deg1] == 0)
return p;
return p.mod(this).gcd(this);
}
Poly pow(long n, Poly polyMod) {
int deg = this.deg();
if (val[deg] == 0)
return new Poly(mod);
Poly ret = new Poly(mod);
ret.add(0, 1);
Poly pow = new Poly(mod);
for (int i = 0; i < val.length; ++i) {
pow.add(i, val[i]);
}
for (; n > 0; n >>= 1, pow.mul(pow), pow = pow.mod(polyMod)) {
if (n % 2 == 1) {
ret.mul(pow);
ret = ret.mod(polyMod);
}
}
return ret;
}
}
public static long inv(long a, long mod) {
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
return p < 0 ? p + mod : p;
}
// static long inv(long a, long mod) {
// return pow(a, mod - 2, mod);
// }
static long pow(long a, long n, long mod) {
long ret = 1;
for (; n > 0; n >>= 1, a = (a * a) % mod) {
if (n % 2 == 1) {
ret = (ret * a) % mod;
}
}
return ret;
}
static void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
class Scanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
return (int) nextLong();
}
}
}