[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

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

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai