AcWing 887. 求组合数 III
原题链接
简单
作者:
gongjin
,
2023-01-11 14:12:29
,
所有人可见
,
阅读 117
卢卡斯定理 求组合数③ JAVA实现
import java.util.Scanner;
class Main {
static int p;
public static int qmi(long a, long k) {
int res = 1 % p;
while (k > 0) {
if ((k & 1) == 1) res = (int) ((long) res * a % p);
a = (int) a * a % p;
k >>= 1;
}
return res;
}
public static int c(long a, long b) {
int res = 1;
long i, j;
for (i = 1, j = a; i <= b; i++, j--) {
res = (int) ((long) res * j % p);
res = (int) ((long) res * qmi(i, p - 2) % p);
}
return res;
}
public static int lucas(long a, long b) {
if (a < p && b < p) {
return c(a, b);
} else {
return (int) ((long) lucas(a % p, b % p) * lucas(a / p, b / p) % p);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
long a = scanner.nextLong();
long b = scanner.nextLong();
p = scanner.nextInt();
System.out.println(lucas(a, b));
}
}
}