AcWing 888. 求组合数 IV
原题链接
简单
作者:
gongjin
,
2023-01-11 15:16:35
,
所有人可见
,
阅读 125
筛选质因子求组合数 JAVA实现
import java.math.BigInteger;
import java.util.Scanner;
class Main {
static int N = 5010;
static int[] primes = new int[N];
static boolean[] st = new boolean[N];
static int[] sum = new int[N];
static int cnt;
//线性筛选素数
public static void getPrimes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
//a!中含有p的个数
public static int get(int a, int p) {
int res = 0;
while (a > 0) {
res += a / p;
a /= p;
}
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
//筛选<=a的素数
getPrimes(a);
for (int i = 0; i < cnt; i++) {
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
BigInteger res = new BigInteger("1");
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < sum[i]; j++) {
BigInteger tmp = new BigInteger(primes[i] + "");
res = res.multiply(tmp);
}
}
System.out.println(res);
}
}