1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
pub fn powmod(x: u64, p: u64, m: u64) -> u64 {
let mut res = x;
for _ in 1..p {
res = (res * x) % m;
}
return res;
}
pub fn adler64(buf: &[u8]) -> u64 {
let mod64 = 4294967291u64;
let mut s1 = 1u64;
let mut s2 = 0u64;
for n in buf {
s1 = (s1 + *n as u64) % mod64;
s2 = (s2 + s1) % mod64;
}
return (s2 << 32) | s1;
}
pub fn inverse_mod(x: i64, m: i64) -> i64 {
let (_, x, _) = extended_gcd(x, m);
return (x % m + m) % m;
}
pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
if a == 0 {
return (b, 0, 1);
}
let (d, x, y) = extended_gcd(b % a, a);
return (d, y - (b / a) * x, x);
}
|
