2282.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2282 on 2006-07-23 at 01:57:50 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int K = 440;

bool pr[K];
int p[K], pn = 0, pp[K][K], mul[K];

int64 d[K][K];
void parse(int);
void dfs(int, int);

int main()
{
	int i, j, n, k;
	
	memset(pr, true, sizeof(pr));
	pr[0] = pr[1] = false;
	for(i = 2; i < K; i++) {
		if(!pr[i]) continue;
		p[pn++] = i;
		for(j = 2*i; j < K; j += i) pr[j] = false;
	}
	memset(pp, 0, sizeof(pp));
	for(i = 0; i < K; i++) {
		parse(i); memset(mul, 0, sizeof(mul));
		for(j = 0; 2*j <= i; j++) dfs(i, j);
	}
	while(scanf("%d %d", &n, &k) != EOF) {
		if(2*k > n) k = n-k;
		printf("%lld\n", d[n][k]);
	}
	
	return 0;
}

void parse(int n)
{
	int i, m = n;
	for(i = 0; n > 1; i++)
		while(n % p[i] == 0) { n /= p[i]; pp[m][i]++; }
}
void dfs(int n, int k)
{
	d[n][k] = 1;
	if(k == 0) return;
	int i;
	for(i = 0; i < pn; i++) {
		mul[i] += pp[n-k+1][i]-pp[k][i];
		d[n][k] *= mul[i]+1;
	}
}