結果
| 問題 |
No.950 行列累乗
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2019-12-26 00:02:54 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,741 bytes |
| コンパイル時間 | 4,427 ms |
| コンパイル使用メモリ | 88,608 KB |
| 実行使用メモリ | 61,244 KB |
| 最終ジャッジ日時 | 2024-10-01 12:58:09 |
| 合計ジャッジ時間 | 14,490 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 30 WA * 27 |
ソースコード
package adv2019;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
public class D21X {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int P = ni();
int[][] a = new int[2][];
for(int i = 0;i < 2;i++) a[i] = na(2);
int[][] b = new int[2][];
for(int i = 0;i < 2;i++) b[i] = na(2);
long da = (long)a[0][0] * a[1][1] - (long)a[0][1] * a[1][0];
long db = (long)b[0][0] * b[1][1] - (long)b[0][1] * b[1][0];
da %= P;
if(da < 0)da += P;
db %= P;
if(db < 0)db += P;
{
boolean ok = true;
for(int i = 0;i < 2;i++) {
for(int j = 0;j < 2;j++) {
if(a[i][j] != b[i][j])ok = false;
}
}
if(ok) {
out.println(1);
return;
}
}
if(da == 0) {
if(db != 0) {
out.println(-1);
return;
}else {
long tra = a[0][0] + a[1][1];
long trb = b[0][0] + b[1][1];
tra %= P;
trb %= P;
if(tra != 0) {
long e = bsgs(tra, trb, P);
if(e == -1) {
out.println(-1);
return;
}else {
for(int k = 0;k < 2;k++) {
for(int l = 0;l < 2;l++) {
if(pow(a[k][l], e, P) != b[k][l]) {
out.println(-1); return;
}
}
}
out.println(e == 0 ? order((int)tra, P) : e);
return;
}
}else {
boolean ok = true;
for(int i = 0;i < 2;i++) {
for(int j = 0;j < 2;j++) {
if(b[i][j] != 0) {
ok = false;
}
}
}
if(ok) {
out.println(2);
}else {
out.println(-1);
}
return;
}
}
}
long e = bsgs(da, db, P);
if(e == -1) {
out.println(-1);
return;
}
long m = order((int)da, P);
int[][] am = pow(a, m, P);
int[][] br = mul(b, pow(inv(a, P), e, P), P);
long ans = bsgs(am, br, P, e == 0);
if(ans == -1) {
out.println(-1);
}else {
out.println(ans*m+e);
}
}
static int[][] inv(int[][] a, int p)
{
long D = (long)a[0][0] * a[1][1] - (long)a[1][0] * a[0][1];
D %= p;
if(D < 0)D += p;
D = invl(D, p);
return new int[][] {
{(int)(a[1][1] * D % p), (int)((p-a[0][1]) * D % p)},
{(int)((p-a[1][0]) * D % p), (int)(a[0][0] * D % p)}
};
}
public static long bsgs(int[][] alpha, int[][] beta, int p, boolean shift)
{
int m = (int)Math.sqrt(p)+1;
Map<Long, Integer> table = new HashMap<Long, Integer>();
int[][] E = shift ? alpha : new int[][]{{1, 0}, {0, 1}};
for(int j = 0;j < m;j++){
long code = 0;
for(int k = 0;k < 2;k++) {
for(int l = 0;l < 2;l++) {
code = code * 1000000009 + E[k][l];
}
}
table.putIfAbsent(code, j);
E = mul(E, alpha, p);
}
int[][] ie = inv(E, p);
int[][] g = beta;
for(int i = 0;i < m;i++){
long code = 0;
for(int k = 0;k < 2;k++) {
for(int l = 0;l < 2;l++) {
code = code * 1000000009 + beta[k][l];
}
}
if(table.containsKey(code)) {
return i*m+table.get(code) + (shift ? 1 : 0);
}
g = mul(g, ie, p);
}
return -1;
}
public static int[] pow(int[][] A, int[] v, long e, int mod)
{
int[][] MUL = A;
for(int i = 0;i < v.length;i++)v[i] %= mod;
for(;e > 0;e>>>=1) {
if((e&1)==1)v = mul(MUL, v, mod);
MUL = p2(MUL, mod);
}
return v;
}
// int matrix * int vector
public static int[] mul(int[][] A, int[] v, int mod)
{
int m = A.length;
int n = v.length;
int[] w = new int[m];
for(int i = 0;i < m;i++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * v[k];
sum %= mod;
}
w[i] = (int)sum;
}
return w;
}
// int matrix^2 (cannot ensure negative values)
public static int[][] p2(int[][] A, int mod)
{
int n = A.length;
int[][] C = new int[n][n];
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * A[k][j];
sum %= mod;
}
C[i][j] = (int)sum;
}
}
return C;
}
// 普通の累乗計算セット ここまで
// ret[n]=A^(2^n)
public static int[][][] generateP2(int[][] A, int n, int mod)
{
int[][][] ret = new int[n+1][][];
ret[0] = A;
for(int i = 1;i <= n;i++)ret[i] = p2(ret[i-1], mod);
return ret;
}
// A[0]^e*v
// A[n]=A[0]^(2^n)
public static int[] pow(int[][][] A, int[] v, long e, int mod)
{
for(int i = 0;e > 0;e>>>=1,i++) {
if((e&1)==1)v = mul(A[i], v, mod);
}
return v;
}
public static int[][] mul(int mod, int[][]... a)
{
int[][] base = a[0];
for(int i = 1;i < a.length;i++){
base = mul(base, a[i], mod);
}
return base;
}
// メモ累乗計算セット ここまで
// int行列の和
public static int[][] add(int[][] A, int[][] B, int mod)
{
int m = A.length;
int n = A[0].length;
int[][] C = new int[m][n];
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
C[i][j] = (A[i][j] + B[i][j]) % mod;
}
}
return C;
}
public static int[] add(int[] A, int[] B, int mod)
{
int n = A.length;
int[] C = new int[n];
for(int i = 0;i < n;i++){
C[i] = (A[i] + B[i]) % mod;
}
return C;
}
// A^e
// O(N^3log N)
public static int[][] pow(int[][] A, long e, int mod)
{
int[][] MUL = A;
int n = A.length;
int[][] C = new int[n][n];
for(int i = 0;i < n;i++)C[i][i] = 1;
for(;e > 0;e>>>=1) {
if((e&1)==1)C = mul(C, MUL, mod);
MUL = p2(MUL, mod);
}
return C;
}
public static int[][] mul(int[][] A, int[][] B, int mod)
{
assert A[0].length == B.length;
int m = A.length;
int n = A[0].length;
int o = B[0].length;
int[][] C = new int[m][o];
for(int i = 0;i < m;i++){
for(int j = 0;j < o;j++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * B[k][j];
sum %= mod;
}
C[i][j] = (int)sum;
}
}
return C;
}
public static int order(int a, int p)
{
int q = p-1;
for(int i = 2;i*i <= q;i++) {
while(q % i == 0 && pow(a, q/i, p) == 1) {
q /= i;
}
}
return q;
}
public static long pow(long a, long n, long mod) {
// a %= mod;
long ret = 1;
int x = 63 - Long.numberOfLeadingZeros(n);
for (; x >= 0; x--) {
ret = ret * ret % mod;
if (n << 63 - x < 0)
ret = ret * a % mod;
}
return ret;
}
public static long bsgs(long alpha, long beta, int p)
{
int m = (int)Math.sqrt(p)+1;
long[] table = new long[m];
long val = 1;
for(int j = 0;j < m;j++){
table[j] = val<<32|j;
val = val * alpha % p;
}
Arrays.sort(table);
long ainvm = invl(val, p);
long g = beta;
for(int i = 0;i < m;i++){
int ind = Arrays.binarySearch(table, g<<32);
if(ind < 0)ind = -ind-1;
if(ind < m && table[ind]>>>32 == g){
return i*m+(int)table[ind];
}
g = g * ainvm % p;
}
return -1;
}
public static long invl(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;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
// @Override
// public void run() {
// long s = System.currentTimeMillis();
// solve();
// out.flush();
// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// }
// };
// t.start();
// t.join();
}
public static void main(String[] args) throws Exception { new D21X().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private long[] nal(int n)
{
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = nl();
return a;
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[][] nmi(int n, int m) {
int[][] map = new int[n][];
for(int i = 0;i < n;i++)map[i] = na(m);
return map;
}
private int ni() { return (int)nl(); }
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}