結果

問題 No.950 行列累乗
ユーザー akakimidoriakakimidori
提出日時 2019-12-13 19:31:41
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 3,748 bytes
コンパイル時間 2,429 ms
コンパイル使用メモリ 161,260 KB
実行使用メモリ 254,052 KB
最終ジャッジ日時 2023-09-09 21:31:42
合計ジャッジ時間 56,737 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 27 ms
4,376 KB
testcase_02 AC 453 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1,692 ms
253,856 KB
testcase_06 AC 1,232 ms
254,024 KB
testcase_07 AC 454 ms
4,380 KB
testcase_08 AC 1,646 ms
253,872 KB
testcase_09 AC 550 ms
17,668 KB
testcase_10 AC 464 ms
4,376 KB
testcase_11 AC 463 ms
4,376 KB
testcase_12 AC 462 ms
4,380 KB
testcase_13 AC 1,589 ms
253,888 KB
testcase_14 AC 1,447 ms
253,892 KB
testcase_15 AC 463 ms
4,376 KB
testcase_16 AC 640 ms
17,612 KB
testcase_17 WA -
testcase_18 AC 1 ms
4,376 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 1,463 ms
253,888 KB
testcase_22 WA -
testcase_23 AC 1,478 ms
254,028 KB
testcase_24 AC 1,487 ms
253,956 KB
testcase_25 AC 1,573 ms
254,032 KB
testcase_26 AC 1,443 ms
253,952 KB
testcase_27 AC 1,438 ms
254,028 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 1,431 ms
253,948 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 1,437 ms
254,028 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 85 ms
4,376 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 90 ms
4,380 KB
testcase_40 AC 1,718 ms
253,812 KB
testcase_41 AC 1,685 ms
253,988 KB
testcase_42 AC 1,385 ms
253,884 KB
testcase_43 WA -
testcase_44 WA -
testcase_45 AC 1,336 ms
253,780 KB
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 AC 0 ms
4,376 KB
testcase_56 WA -
testcase_57 AC 1 ms
4,380 KB
testcase_58 WA -
testcase_59 AC 150 ms
4,376 KB
testcase_60 AC 149 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;

fn mod_pow(r: u64, mut n: u64, p: u64) -> u64 {
    assert!(r < p);
    let mut t = 1;
    let mut s = r;
    while n > 0 {
        if n & 1 == 1 {
            t = t * s % p;
        }
        s = s * s % p;
        n >>= 1;
    }
    t
}

fn inv(a: u64, p: u64) -> u64 {
    assert!(0 < a && a < p);
    mod_pow(a, p - 2, p)
}

fn log(x: u64, a: u64, p: u64) -> u64 {
    assert!(x < p && a < p);
    if x == 0 {
        return if a == 0 {0} else {p};
    }
    let sq = (p as f64).sqrt() as u64 + 1;
    let mut map = std::collections::HashMap::new();
    for i in (0..sq).rev() {
        map.insert(a * mod_pow(inv(x, p), i, p), i);
    }
    let mut k = 1;
    let x = mod_pow(x, sq, p);
    let mut ans = p;
    for i in 0..sq {
        if let Some(&v) = map.get(&k) {
            ans = std::cmp::min(ans, (i * sq + v) % (p - 1));
        }
        k = k * x % p;
    }
    return ans;
}

type M = [[u64; 2]; 2];

fn matmul(a: &M, b: &M, p: u64) -> M {
    let mut c = [[0; 2]; 2];
    for (c, a) in c.iter_mut().zip(a.iter()) {
        for (a, b) in a.iter().zip(b.iter()) {
            for (c, b) in c.iter_mut().zip(b.iter()) {
                *c = (*c + *a * *b) % p;
            }
        }
    }
    c
}

fn matmul_s(a: &M, x: u64, p: u64) -> M {
    let mut c = [[0; 2]; 2];
    for (c, a) in c.iter_mut().zip(a.iter()) {
        for (c, a) in c.iter_mut().zip(a.iter()) {
            *c = *a * x % p;
        }
    }
    c
}

fn mat_pow(a: &M, mut n: u64, p: u64) -> M {
    let mut t = [[0; 2]; 2];
    t[0][0] = 1;
    t[1][1] = 1;
    let mut s = a.clone();
    while n > 0 {
        if n & 1 == 1 {
            t = matmul(&t, &s, p);
        }
        s = matmul(&s, &s, p);
        n >>= 1;
    }
    t
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let p: u64 = it.next().unwrap().parse().unwrap();
    let mut a: M = [[0; 2]; 2];
    let mut b: M = [[0; 2]; 2];
    for i in 0..2 {
        for j in 0..2 {
            a[i][j] = it.next().unwrap().parse().unwrap();
        }
    }
    for i in 0..2 {
        for j in 0..2 {
            b[i][j] = it.next().unwrap().parse().unwrap();
        }
    }
    if a == b {
        println!("1");
        return;
    }
    let det = (a[0][0] * a[1][1] + p * p - a[0][1] * a[1][0]) % p;
    if det == 0 {
        let x = (a[0][0] + a[1][1]) % p;
        let mut y = p;
        for i in 0..2 {
            for j in 0..2 {
                if a[i][j] != 0 {
                    y = std::cmp::min(y, log(x, a[i][j], p));
                }
            }
        }
        if y < p && b == matmul_s(&a, y, p) {
            println!("{}", y);
        } else {
            println!("-1");
        }
    } else {
        let idet = inv(det, p);
        let ia = matmul_s(&[[a[1][1], (p - a[0][1]) % p], [(p - a[1][0]) % p, a[0][0]]], idet, p);
        assert!(matmul(&a, &ia, p) == [[1, 0], [0, 1]]);
        let sq = 3_000_000;
        let mut map = std::collections::HashMap::new();
        let mut v = matmul(&b, &mat_pow(&ia, sq - 1, p), p);
        for i in (0..sq).rev() {
            map.insert(v, i);
//            println!("[[{}, {}], [{}, {}]]", v[0][0], v[0][1], v[1][0], v[1][1]);
            v = matmul(&v, &a, p);
        }
        let mut k = [[1, 0], [0, 1]];
        let x = mat_pow(&a, sq, p);
        let mut ans = sq * sq;
        for i in 0..sq {
            if let Some(&v) = map.get(&k) {
                ans = std::cmp::min(ans, sq * i + v);
            }
            k = matmul(&k, &x, p);
        }
        if ans < sq * sq {
            println!("{}", ans);
        } else {
            println!("-1");
        }
    }
}

fn main() {
    run();
}
0