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的最小因子)
#include <iostream>
using namespace std;
#define M 1000005
int pf[M]; //pf[i]储存i的最大素因子
bool hash[M];
int main()
{
int i, j, n, k = 0, a, b, tp, q;
bool flag;
/******************素数筛法******************/
for (i = 2; i < M; i++)
{
if (!hash[i])
{
pf[i] = i;
for (j = i << 1; j < M; j += i)
if (!hash[j])
hash[j] = true, pf[j] = i;
}
}
/******************素数筛法******************/
while (~scanf ("%d", &n))
{
flag = false;
a = b = 1;
while (n > 1) //将n进行素数分解
{
tp = 1;
q = pf[n]; //获取n的最大因子
while (n % q == 0) //求有多少个q因子
{
n /= q;
if (n > b) //b是拿到的最多的分量
b = n;
tp++;
}
a *= tp; //简单组合数学
}
printf ("%d %d\n", a-1, b);
}
return 0;
}
http://acm.fzu.edu.cn/problem.php?pid=1753
题意：求多个组合数的最大公约数
思路：求各组组合数的各个素因子个数，以少为主，因为要的是公约数嘛，最后乘起来即可
求N！里包含某素数因子p的个数，就可以这样求。
while(n>0)
{
x+=n/p;
n/=p;
}
不理解请看：求N!的素因子个数的一个例子：
http://972169909-qq-com.iteye.com/blog/1126188
#include <iostream>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 100005
int 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;
}
- 大小: 8.4 KB
相关文章
