【素数筛法总结】fzu 1607 + fzu 1753

【素数筛法小结】fzu 1607 + fzu 1753
KIDx 的解题报告
http://acm.fzu.edu.cn/problem.php?pid=1607
题意：求n平均分成m份(m>1)，问有多少种分法，以及平均的分量最多可以达到多少？

多少种分法：
求n的因子的组合数即可，由于m>1所以【所有因子取0个的情况不包括】
例如：n中有3个素因子p1,2个素因子p2，p1可以取0个，1个，2个，3个【4种情况】，p2可以取0个，1个，2个【3种情况】，所以分法 = 4*3-1 = 11

平均达到最大值：
n/(n的最小素因子)

求N！里包含某素数因子p的个数，就可以这样求。
while(n>0)
{
    x+=n/p;
    n/=p;
}
不理解请看：求N!的素因子个数的一个例子：
http://972169909-qq-com.iteye.com/blog/1126188

另外推荐这题：http://poj.org/problem?id=2992
需要预处理求n！的各个素因子个数，因为n比较小，可以开数组预处理存放后再用


#include <iostream>using namespace std;#define LL __int64#define inf 0x3fffffff#define M 100005int p[10005], num[M], ni[155], mi[155];    //num[i]表示所求中有多少个i因子bool flag;int main(){LL ans;memset (num, 0, sizeof(num));int i, j, k = 0, t, n, m, tp, count, mins;/***********素数筛法***********//**********M以内的素数存到p数组**********/for (i = 2; i < M; i++){if (!num[i]){p[k++] = i;for (j = i << 1; j < M; j+=i)if (!num[j])num[j] = 1;}}/**********M以内的素数存到p数组**********//***********素数筛法***********/while (~scanf ("%d", &t)){memset (num, -1, sizeof(num));mins = inf;for (i = 0; i < t; i++){scanf ("%d%d", ni+i, mi+i);if (mins > ni[i])//这个是必须的，自己想！mins = ni[i];}for (j = 0; j < t; j++){n = ni[j];m = mi[j];for (i = 0; i < k; i++){if (p[i] > mins)//必须的！break;count = 0;/*****n!中有多少个p[i]*****/if (n >= p[i]){tp = n;while (tp){tp /= p[i];count += tp;}}/*****m!中有多少个p[i]*****/if (m >= p[i]){tp = m;while (tp){tp /= p[i];count -= tp;//因为是分母，所以减}}/*****(n-m)!中有多少个p[i]*****/if (n - m >= p[i]){tp = n - m;while (tp){tp /= p[i];count -= tp;}}/****得到的count就是该组合数中有多少个p[i]****/if (num[p[i]] == -1 || count < num[p[i]])num[p[i]] = count;}}ans = 1;for (i = 0; i < k; i++){if (num[p[i]] <= 0)continue;for (j = 0; j < num[p[i]]; j++)ans *= p[i];}printf ("%I64d\n", ans);}return 0;}