[POJ 2992] Divisors【欧拉筛】
Problem:
| Time Limit: 1000MS | Memory Limit: 65536K |
Description
Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?
Input
The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.
Output
For each instance, output a line containing exactly one integer -- the number of distinct divisors of Cnk. For the input instances, this number does not exceed 263 - 1.
Sample Input
5 1 6 3 10 4
Sample Output
2 6 16
Source
CTU Open 2005
Solution:
先用欧拉筛筛出 [2, 431] 上的素数，再将阶乘整体分解质因数（若逐个分解则会 TLE），套用因数个数公式即可。
【因数个数公式】
对一个大于 1 的正整数 n 分解质因数：
则 n 的因数个数 f(n) 满足：
Code: O(T(N+PlogN)), 其中P为素数个数 [168K, 954MS]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int UPRANGE = 431;
int prm[UPRANGE >> 1], prmSize;
bool isprm[UPRANGE + 2];
inline void initPrime(){
memset(isprm, 1, sizeof(isprm));
isprm[0] = isprm[1] = 0, prmSize = 0;
for(register int i = 2; i <= UPRANGE; i++){
if(isprm[i]) prm[++prmSize] = i;
for(register int j = 1; j <= prmSize && i * prm[j] <= UPRANGE; j++){
isprm[i * prm[j]] = 0;
if(i % prm[j] == 0) break;
}
}
}
int n, k;
int cntPrm[UPRANGE >> 1];
inline void cntAsFactorial(int x, int weight){
for(register int i = 1; i <= prmSize; i++){
int tmp = x;
while(tmp) cntPrm[i] += weight * (tmp /= prm[i]);
} // 1..x has [x/p] multipliers of p, [x/p^2] multipliers of p^2, etc.
}
int main(){
initPrime();
while(scanf("%d%d", &n, &k) != EOF){
if(k > (n >> 1)) k = n - k;
long long ans = 1;
memset(cntPrm, 0, sizeof(cntPrm));
cntAsFactorial(n, 1), cntAsFactorial(n - k, -1), cntAsFactorial(k, -1);
for(register int i = 1; i <= prmSize; i++) ans *= cntPrm[i] + 1;
printf("%lld\n", ans);
}
return 0;
}
发表评论