[POJ 2992] Divisors【欧拉筛】

• 2017-12-30
• 0
• 0

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

【因数个数公式】

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;
}
```

评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai