AcWing 888. 求组合数 IV java
原题链接
简单
作者:
我是傻吊
,
2021-05-25 09:52:07
,
所有人可见
,
阅读 324
import java.util.*;
import java.math.BigInteger;
public class Main{
static final int N = 5010;
static int[] primes = new int[N];
static boolean st[] = new boolean[N];
static int cnt;
static int[] sum = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
// BigInteger a = sc.nextBigInteger();
// BigInteger b = sc.nextBigInteger();
int a = sc.nextInt();
int b = sc.nextInt();
////通过模板筛素数
getPrime(a);
for(int i = 0; i < cnt; i++){
int p = primes[i];
// //拿到这个当前的素数
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
//计算a!,(a-b)!,b!中质数因子p的个数,就是上面的公式1
}
BigInteger res = BigInteger.valueOf(1);
for(int i = 0; i < cnt; i++){
BigInteger prime = BigInteger.valueOf(primes[i]);
for(int j = 0; j < sum[i]; j++){
res = res.multiply(prime);
// System.out.println("prime:" + prime);
// System.out.println(res+"===");
}
}
// for(int i = 0; i < cnt; i++){
// System.out.print(primes[i] + " ");
// }
// for(int i = 0; i < cnt; i++){
// System.out.print(sum[i] + " ");
// }
System.out.println(res);
}
////求n!中素数p的个数,这就是上面下取整的那个数学公式,不重不漏那个。
public static int get(int n, int p){
int cnt = 0;
while(n > 0){
cnt += n / p;
n = n / p;
}
return cnt;
}
public static void getPrime(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[i * primes[j]] = true;
if(i % primes[j] == 0){
break;
}
}
}
}
}
hh 写的不错