結果
| 問題 |
No.950 行列累乗
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2019-12-13 23:22:21 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 17,985 bytes |
| コンパイル時間 | 2,817 ms |
| コンパイル使用メモリ | 91,000 KB |
| 実行使用メモリ | 65,876 KB |
| 最終ジャッジ日時 | 2024-06-27 21:02:33 |
| 合計ジャッジ時間 | 14,166 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 WA * 1 |
| other | AC * 36 WA * 20 RE * 1 |
ソースコード
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) {
new Main().run();
}
long MOD;
class K {// quadratic field
long a, b, base;
public K(long a, long b, long base) {
this.a = (a % MOD + MOD) % MOD;
this.b = (b % MOD + MOD) % MOD;
this.base = (base % MOD + MOD) % MOD;
}
K add(K o) {
return new K((a + o.a) % MOD, (b + o.b) % MOD, base);
}
K sub(K o) {
return new K((a - o.a + MOD) % MOD, (b - o.b + MOD) % MOD, base);
}
K mul(K o) {
return new K((a * o.a + b * o.b * base % MOD) % MOD, (a * o.b + o.a * b) % MOD, base);
}
// (a+b√w)/(c+d√w)=(a+b√w)(c-d√w)/(cc-ddw)
K div(K o) {
long det = o.det();
K ret = this.mul(new K(o.a, -o.b, base));
ret.a = ret.a * inv(det, MOD) % MOD;
ret.b = ret.b * inv(det, MOD) % MOD;
return ret;
}
K rev() {
return new K(1, 0, base).div(this);
}
long det() {
return (a * a % MOD - b * b % MOD * base % MOD + MOD) % MOD;
}
boolean equiv(K o) {
return a == o.a && b == o.b;
}
List<Long> toList() {
List<Long> list = new ArrayList<Long>();
list.add(a);
list.add(b);
return list;
}
}
long[][] pow(long[][] a, long n) {
long[][] ret = new long[2][2];
ret[0][0] = ret[1][1] = 1;
for (; n > 0; n >>= 1, a = mul(a, a)) {
if (n % 2 == 1)
ret = mul(ret, a);
}
return ret;
}
K[][] mul(K coe, K[][] a) {
K[][] ret = new K[a.length][a[0].length];
for (int i = 0; i < a.length; ++i)
for (int j = 0; j < a[i].length; ++j)
ret[i][j] = a[i][j].mul(coe);
return ret;
}
long[][] mul(long[][] a, long[][] b) {
long[][] ret = new long[a.length][b[0].length];
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < b[i].length; ++j) {
for (int k = 0; k < a[i].length; ++k) {
ret[i][j] += a[i][k] * b[k][j] % MOD;
ret[i][j] = (ret[i][j] % MOD + MOD) % MOD;
}
}
}
return ret;
}
K[][] mul(K[][] a, K[][] b) {
K[][] ret = new K[a.length][b[0].length];
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret[i][j] = new K(0, 0, a[0][0].base);
}
}
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < b[i].length; ++j) {
for (int k = 0; k < a[i].length; ++k) {
ret[i][j] = ret[i][j].add(a[i][k].mul(b[k][j]));
}
}
}
return ret;
}
long det(long[][] a) {
return (a[0][0] * a[1][1] % MOD - a[0][1] * a[1][0] % MOD + MOD) % MOD;
}
K det(K[][] a) {
return (a[0][0].mul(a[1][1])).sub(a[0][1].mul(a[1][0]));
}
long[][] rndmat(long p) {
long[][] ret = new long[2][2];
Random rnd = new Random();
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
ret[i][j] = rnd.nextInt((int) 7);
return ret;
}
void run() {
// long p = (long) 7;
// MOD = p;
// for (int i = 0;; ++i) {
// long[][] a = rndmat(p);
// long[][] b = rndmat(p);
// long ans0 = exact(a, b, p);
// long ans1 = solve(a, b, p);
// if (ans1 != -99 && ans0 != ans1) {
// tr(a, b);
// tr(ans0, ans1);
// }
// }
//
Scanner sc = new Scanner(System.in);
long p = sc.nextLong();
long[][] a = new long[2][2];
long[][] b = new long[2][2];
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
a[i][j] = sc.nextLong();
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
b[i][j] = sc.nextLong();
// System.out.println(exact(a, b, p));
System.out.println(solve(a, b, p));
}
long solve2(long[][] a, long[][] b, long p) {
if (equiv(a, b))
return 1;
if (p == 2)
return exact(a, b, p);
Scanner sc = new Scanner(System.in);
MOD = p;
long w = (a[0][0] * a[0][0] % MOD - 2 * a[0][0] * a[1][1] % MOD + a[1][1] * a[1][1] % MOD
+ 4 * a[0][1] * a[1][0] % MOD) % MOD;
long det0 = det(a);
long det1 = det(b);
if (det0 == 0 && det1 > 0)
return -1;
K eigen1 = new K(inv(2, MOD) * (a[0][0] + a[1][1]) % MOD, -inv(2, MOD), w);
K eigen2 = new K(inv(2, MOD) * (a[0][0] + a[1][1]) % MOD, inv(2, MOD), w);
K[][] S = new K[2][2];
K[][] J = new K[2][2];
K[][] eigenvec1 = new K[2][1];
K[][] eigenvec2 = new K[2][1];
K[][] ak = new K[][] { { new K(a[0][0], 0, w), new K(a[0][1], 0, w) },
{ new K(a[1][0], 0, w), new K(a[1][1], 0, w) } };
K[][] bk = new K[][] { { new K(b[0][0], 0, w), new K(b[0][1], 0, w) },
{ new K(b[1][0], 0, w), new K(b[1][1], 0, w) } };
if (a[1][0] == 0) {
// {{a,b}
// {0,d}}
eigen1 = new K(a[0][0], 0, w);
eigen2 = new K(a[1][1], 0, w);
eigenvec1 = new K[][] { { new K(1, 0, w) }, { new K(0, 0, w) } };
eigenvec2 = new K[][] { { new K((MOD - a[0][1]) % MOD, 0, w) },
{ new K(((a[0][0] - a[1][1]) % MOD + MOD) % MOD, 0, w) } };
S = new K[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } };
J = new K[][] { { eigen1, new K(0, 0, w) }, { new K(0, 0, w), eigen2 } };
// if (!equiv(mul(a, eigenvec1), mul(eigen1, eigenvec1))
// || !equiv(mul(a, eigenvec2), mul(eigen2, eigenvec2))) {
// tr(a, eigenvec1, eigen1, MOD, mul(a, eigenvec1), mul(eigen1, eigenvec1));
// tr(a, eigenvec2, eigen2, MOD, mul(a, eigenvec2), mul(eigen2, eigenvec2));
// throw new AssertionError();
// }
} else if (eigen1 != eigen2) {
eigenvec1 = new K[][] { { new K(a[0][0] - a[1][1], -1, w) }, { new K(2 * a[1][0], 0, w) } };
eigenvec2 = new K[][] { { new K(a[0][0] - a[1][1], +1, w) }, { new K(2 * a[1][0], 0, w) } };
S = new K[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } };
J = new K[][] { { eigen1, new K(0, 0, w) }, { new K(0, 0, w), eigen2 } };
// if (!equiv(mul(a, eigenvec1), mul(eigen1, eigenvec1))
// || !equiv(mul(a, eigenvec2), mul(eigen2, eigenvec2))) {
// tr(a, eigenvec1, eigen1, MOD, mul(a, eigenvec1), mul(eigen1, eigenvec1));
// tr(a, eigenvec2, eigen2, MOD, mul(a, eigenvec2), mul(eigen2, eigenvec2));
// throw new AssertionError();
// }
} else {
eigenvec2 = new K[2][1];
if (!eigen1.equiv(new K(0, 0, w))) {
eigenvec2 = new K[][] { { new K(a[0][0] - a[1][1], 1, w) }, { new K(2 * a[1][0], 0, w) } };
} else {
eigenvec2 = new K[][] { { new K(MOD - a[0][1], 0, w) }, { new K(a[0][0], 0, w) } };
}
// if (!equiv(mul(a, eigenvec2), mul(eigen1, eigenvec2))) {
// tr(a, eigenvec2, MOD, mul(a, eigenvec2));
// throw new AssertionError();
// }
K[][] tmp = new K[2][2];
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
tmp[i][j] = ak[i][j];
tmp[0][0] = tmp[0][0].sub(eigen1);
tmp[1][1] = tmp[1][1].sub(eigen1);
eigenvec1 = mul(tmp, eigenvec2);
// if (eigenvec1[0][0] == 0 && eigenvec1[1][0] == 0)
// throw new AssertionError();
S = new K[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } };
J = new K[][] { { eigen1, new K(1, 0, w) }, { new K(0, 0, w), eigen2 } };
}
bk = mul(bk, S);
bk = mul(invmat(S), bk);
if (b[1][0] != 0 && J[1][0].equiv(new K(0, 0, w))) {
return -1;
}
if (eigen1 != eigen2 && !eigen1.equiv(new K(0, 0, w)) && !eigen2.equiv(new K(0, 0, w))) {
if (b[0][1] != 0 || b[1][0] != 0)
return -1;
}
if ((b[0][0] > 0 && J[0][0].equiv(new K(0, 0, w))) || (b[1][1] > 0 && J[1][1].equiv(new K(0, 0, w))))
return -1;
if ((!J[0][1].mul(J[0][0].add(J[1][0])).equiv(new K(0, 0, w)) && b[0][1] == 0)
|| (J[0][1].equiv(new K(0, 0, w)) && b[0][1] != 0))
return -1;
// A=[a b
// 0 c]
// A^(k+1)=[a^(k+1) b(a+c)^k
// 0 c^(k+1)]
long sol1 = discretelog(J[0][0], bk[0][0]);
long sol2 = discretelog(J[1][1], bk[1][1]);
if (sol1 == -1 || sol2 == -1)
return -1;
long ord1 = ord(J[0][0], MOD);
long ord2 = ord(J[1][1], MOD);
long ans1 = sol1;
long ans2 = sol2;
if (Math.abs(ans1 - ans2) % gcd(ord1, ord2) != 0)
return -1;
while (ans1 != ans2) {
if (ans1 < ans2) {
ans1 += (ans2 - ans1 + ord1 - 1) / ord1 * ord1;
} else {
ans2 += (ans1 - ans2 + ord2 - 1) / ord2 * ord2;
}
}
while (!equiv(pow(J, ans1), bk)) {
ans1 += lcm(ord1, ord2);
ans2 += lcm(ord1, ord2);
}
return ans1;
}
long solve(long[][] a, long[][] b, long p) {
if (equiv(a, b))
return 1;
if (p == 2)
return exact(a, b, p);
Scanner sc = new Scanner(System.in);
MOD = p;
long w = (a[0][0] * a[0][0] % MOD - 2 * a[0][0] * a[1][1] % MOD + a[1][1] * a[1][1] % MOD
+ 4 * a[0][1] * a[1][0] % MOD) % MOD;
if (!isQuadraticResidue(w)) {
return solve2(a, b, p);
// throw new AssertionError();
}
w = sqrt((w + MOD) % MOD, p);
long det0 = det(a);
long det1 = det(b);
if (det0 == 0 && det1 > 0)
return -1;
long eigen1 = inv(2, MOD) * (-w + a[0][0] + a[1][1]) % MOD;
long eigen2 = inv(2, MOD) * (+w + a[0][0] + a[1][1]) % MOD;
long[][] S = new long[2][2];
long[][] J = new long[2][2];
long[][] eigenvec1 = new long[2][1];
long[][] eigenvec2 = new long[2][1];
if (a[1][0] == 0) {
// {{a,b}
// {0,d}}
eigen1 = a[0][0];
eigen2 = a[1][1];
eigenvec1 = new long[][] { { 1 }, { 0 } };
eigenvec2 = new long[][] { { (MOD - a[0][1]) % MOD }, { ((a[0][0] - a[1][1]) % MOD + MOD) % MOD } };
S = new long[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } };
J = new long[][] { { eigen1, 0 }, { 0, eigen2 } };
// if (!equiv(mul(a, eigenvec1), mul(eigen1, eigenvec1))
// || !equiv(mul(a, eigenvec2), mul(eigen2, eigenvec2))) {
// tr(a, eigenvec1, eigen1, MOD, mul(a, eigenvec1), mul(eigen1, eigenvec1));
// tr(a, eigenvec2, eigen2, MOD, mul(a, eigenvec2), mul(eigen2, eigenvec2));
// throw new AssertionError();
// }
} else if (eigen1 != eigen2) {
eigenvec1 = new long[][] { { (MOD - (-a[0][0] + a[1][1] + w) % MOD) % MOD }, { 2 * a[1][0] % MOD } };
eigenvec2 = new long[][] { { (MOD - (-a[0][0] + a[1][1] - w) % MOD) % MOD }, { 2 * a[1][0] % MOD } };
S = new long[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } };
J = new long[][] { { eigen1, 0 }, { 0, eigen2 } };
// if (!equiv(mul(a, eigenvec1), mul(eigen1, eigenvec1))
// || !equiv(mul(a, eigenvec2), mul(eigen2, eigenvec2))) {
// tr(a, eigenvec1, eigen1, MOD, mul(a, eigenvec1), mul(eigen1, eigenvec1));
// tr(a, eigenvec2, eigen2, MOD, mul(a, eigenvec2), mul(eigen2, eigenvec2));
// throw new AssertionError();
// }
} else {
eigenvec2 = new long[2][1];
if (eigen1 != 0) {
eigenvec2 = new long[][] { { (MOD - (-a[0][0] + a[1][1] - w) % MOD) % MOD }, { 2 * a[1][0] % MOD } };
} else {
eigenvec2 = new long[][] { { (MOD - a[0][1]) % MOD }, { a[0][0] } };
}
// if (!equiv(mul(a, eigenvec2), mul(eigen1, eigenvec2))) {
// tr(a, eigenvec2, MOD, mul(a, eigenvec2));
// throw new AssertionError();
// }
long[][] tmp = new long[][] { { a[0][0] - eigen1, a[0][1] }, { a[1][0], a[1][1] - eigen1 } };
eigenvec1 = mul(tmp, eigenvec2);
if (eigenvec1[0][0] == 0 && eigenvec1[1][0] == 0)
throw new AssertionError();
S = new long[][] { { eigenvec1[0][0], eigenvec2[0][0] }, { eigenvec1[1][0], eigenvec2[1][0] } };
J = new long[][] { { eigen1, 1 }, { 0, eigen2 } };
}
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
J[i][j] = (J[i][j] % MOD + MOD) % MOD;
b[i][j] = (b[i][j] % MOD + MOD) % MOD;
}
}
b = mul(b, S);
b = mul(invmat(S), b);
if (b[1][0] != 0 && J[1][0] == 0) {
return -1;
}
if (eigen1 != eigen2 && eigen1 != 0 && eigen2 != 0) {
if (b[0][1] != 0 || b[1][0] != 0)
return -1;
}
if ((b[0][0] > 0 && J[0][0] == 0) || (b[1][1] > 0 && J[1][1] == 0))
return -1;
if ((J[0][1] * (J[0][0] + J[1][0]) % MOD != 0 && b[0][1] == 0) || (J[0][1] == 0 && b[0][1] != 0))
return -1;
// A=[a b
// 0 c]
// A^(k+1)=[a^(k+1) b(a+c)^k
// 0 c^(k+1)]
long sol1 = discretelog(J[0][0], b[0][0]);
long sol2 = discretelog(J[1][1], b[1][1]);
if (sol1 == -1 || sol2 == -1)
return -1;
long ord1 = ord(J[0][0], MOD);
long ord2 = ord(J[1][1], MOD);
long ans1 = sol1;
long ans2 = sol2;
if (Math.abs(ans1 - ans2) % gcd(ord1, ord2) != 0)
return -1;
while (ans1 != ans2) {
if (ans1 < ans2) {
ans1 += (ans2 - ans1 + ord1 - 1) / ord1 * ord1;
} else {
ans2 += (ans1 - ans2 + ord2 - 1) / ord2 * ord2;
}
}
while (!equiv(pow(J, ans1), b)) {
ans1 += lcm(ord1, ord2);
ans2 += lcm(ord1, ord2);
}
return ans1;
}
boolean equiv(long[][] a, long[][] b) {
boolean ret = true;
if (a[0].length != b[0].length || a[1].length != b[1].length)
throw new AssertionError();
for (int i = 0; i < a.length; ++i)
for (int j = 0; j < a[0].length; ++j)
ret &= a[i][j] == b[i][j];
return ret;
}
boolean equiv(K[][] a, K[][] b) {
boolean ret = true;
if (a[0].length != b[0].length || a[1].length != b[1].length)
throw new AssertionError();
for (int i = 0; i < a.length; ++i)
for (int j = 0; j < a[0].length; ++j)
ret &= a[i][j].equiv(b[i][j]);
return ret;
}
long exact(long[][] a, long[][] b, long p) {
MOD = p;
for (int i = 1; i < p * p; ++i) {
long[][] pw_a = pow(a, i);
boolean equiv = true;
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k)
equiv &= pw_a[j][k] == b[j][k];
if (equiv)
return i;
}
return -1;
}
long inv(long a, long mod) {
return pow(a, mod - 2);
}
long ord(long a, long p) {
if (a == 0 || a == 1)
return 1;
long ret = p - 1;
for (long div = 2; div * div <= p - 1; ++div) {
if ((p - 1) % div != 0)
continue;
if (pow(a, div) == 1)
ret = Math.min(ret, div);
else if (pow(a, (p - 1) / div) == 1)
ret = Math.min(ret, (p - 1) / div);
}
return ret;
}
long ord(K a, long p) {
long base = a.base;
if (a.equiv(new K(0, 0, base)) || a.equiv(new K(1, 0, base)))
return 1;
long ret = 2 * p - 1;// (a+bw)^2p=a+bw
for (long div = 2; div * div <= 2 * p - 1; ++div) {
if ((p - 1) % div != 0)
continue;
if (pow(a, div).equiv(new K(1, 0, base)))
ret = Math.min(ret, div);
else if (pow(a, (p - 1) / div).equiv(new K(1, 0, base)))
ret = Math.min(ret, (p - 1) / div);
}
return ret;
}
long pow(long a, long n) {
long ret = 1;
for (; n > 0; n >>= 1, a = a * a % MOD) {
if (n % 2 == 1)
ret = ret * a % MOD;
}
return ret;
}
K pow(K a, long n) {
K ret = new K(1, 0, a.base);
for (; n > 0; n >>= 1, a = a.mul(a)) {
if (n % 2 == 1)
ret = ret.mul(a);
}
return ret;
}
K[][] pow(K[][] a, long n) {
K[][] ret = new K[2][2];
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret[i][j] = new K(i == j ? 1 : 0, 0, a[0][0].base);
}
}
for (; n > 0; n >>= 1, a = mul(a, a)) {
if (n % 2 == 1)
ret = mul(ret, a);
}
return ret;
}
// return x s.t. a^x = b && x>0
long discretelog(long a, long b) {
if (a == 1) {
if (b == 1)
return 1;
else
return -1;
} else if (a == 0) {
if (b == 0)
return 1;
else
return -1;
}
// a^(um+v) = b
// a^v = b a^(-m)^u
int m = (int) (Math.sqrt(MOD) + 1);
long pw = 1;
HashMap<Long, Integer> map = new HashMap<>();
for (int v = 0; v <= m; ++v) {
map.put(pw, v);
pw = pw * a % MOD;
}
long ima = pow(inv(a, MOD), m);
long ipw = 1;
for (int i = 0; i <= m; ++i) {
if (map.containsKey(b * ipw % MOD)) {
long ret = i * m + map.get(b * ipw % MOD);
if (ret != 0)
return ret;
}
ipw = ipw * ima % MOD;
}
return -1;
}
// return x s.t. a^x = b && x>0
long discretelog(K a, K b) {
long base = a.base;
if (a.equiv(new K(1, 0, base))) {
if (b.equiv(new K(1, 0, base)))
return 1;
else
return -1;
} else if (a.equiv(new K(0, 0, base))) {
if (b.equiv(new K(0, 0, base)))
return 1;
else
return -1;
}
// a^(um+v) = b
// a^v = b a^(-m)^u
int m = (int) (Math.sqrt(MOD) + 5);
K pw = new K(1, 0, base);
HashMap<List<Long>, Integer> map = new HashMap<>();
for (int v = 0; v <= m; ++v) {
map.put(pw.toList(), v);
pw = pw.mul(a);
}
K ima = pow(a.rev(), m);
K ipw = new K(1, 0, base);
for (int i = 0; i <= m; ++i) {
if (map.containsKey(b.mul(ipw).toList())) {
long get = map.get(b.mul(ipw).toList());
long ret = i * m + get;
if (ret != 0)
return ret;
}
ipw = ipw.mul(ima);
}
return -1;
}
long[][] invmat(long[][] a) {
if (det(a) == 0)
throw new AssertionError();
long[][] ret = new long[2][2];
ret[0][0] = a[1][1];
ret[1][1] = a[0][0];
ret[0][1] = (MOD - a[0][1]) % MOD;
ret[1][0] = (MOD - a[1][0]) % MOD;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
ret[i][j] = ret[i][j] * inv(det(a), MOD) % MOD;
return ret;
}
K[][] invmat(K[][] a) {
long base = a[0][0].base;
if (det(a).equiv(new K(0, 0, base)))
throw new AssertionError();
K[][] ret = new K[2][2];
ret[0][0] = new K(a[1][1].a, a[1][1].b, base);
ret[1][1] = new K(a[0][0].a, a[0][0].b, base);
ret[0][1] = new K(-a[0][1].a, -a[0][1].b, base);
ret[1][0] = new K(-a[1][0].a, -a[1][0].b, base);
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
ret[i][j] = ret[i][j].mul(det(a).rev());
return ret;
}
long gcd(long a, long b) {
if (a > b)
return gcd(b, a);
if (a == 0)
return b;
return gcd(a, b % a);
}
long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
boolean isQuadraticResidue(long a) {
return pow(a, (MOD - 1) / 2) == 1;
}
long sqrt(long a, long p) {
if (a == 0)
return 0;
int b = 0;
while (pow((b * b % p - a + p) % p, (p - 1) / 2) != p - 1)
++b;
long[] d = { 1, 0 };
long[] m = { b, 1 };
long n = (p + 1) / 2;
for (; n > 0; n >>= 1, m = poly_mul(m, m, b, a, p)) {
if (n % 2 == 1)
d = poly_mul(d, m, b, a, p);
}
return d[0];
}
long[] poly_mul(long[] u, long[] v, long b, long a, long p) {
long[] ret = new long[3];
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret[i + j] += u[i] * v[j];
ret[i + j] %= p;
}
}
ret[0] += ret[2] * (b * b - a);
ret[0] %= p;
for (int i = 0; i < ret.length; ++i) {
while (ret[i] < 0)
ret[i] += p;
}
return Arrays.copyOf(ret, 2);
}
void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
}