猩猩散步(素数大数乘 高精度)

题目链接:http://acm.ocrosoft.com/problem.php?cid=2659&pid=3

题目描述
  猩猩,骆驼,还有泡泡经常喜欢在饭后到操场上散步,由于猩猩的走路姿势最突出最显眼,理所应当的成为他们中的主角,所以我的题目就说猩猩散步了。(骆驼和泡泡别有意见哈,和猩猩争啥……)   当然,话说回来,猩猩在OI上的能力也是不容低估的,你看,散步时还会想一道与此相关的问题,这是道经典的不能再经典的问题了。   在一个m×n的矩阵上,猩猩在左下角的顶点出现了,他只能沿着路径向上或者向右走,他的目标是“蠕动”到右上角的顶点,问他有多少路径可以选择。嗯,这个、这个、这个似乎地球人都知道怎么做,但是请注意,我有个条件没给呢!m和n现在的最大范围是50000,这可怎么办?仔细想想吧。
输入
只有一行,包含两个整数m和n,其上限均为50000
输出
由于最后的答案数目过大,所以只检查后100位,输出时每行十个数字,没空格间隔,共十行,如果答案位数没超过100位,则需要在空位上补0。

样例输入

7 4

样例输出

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000330

分析

题意就是求 C(n, m) ,需要用到高精度,可以先将组合数的元素进行素数分解,然后就能方便的用高精度算出答案了。

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define N 100005
typedef long long ll;

int cnt,prime[N],vis[N];
int n,m;
int a[N],p[N],len;

void Prime(int nn)
{
	for(int i=2;i<=nn;i++)
	{
		if(!vis[i]) prime[++cnt] = i;
		for(int j=1;j<=cnt&&i*prime[j]<=nn;j++)
		{
			vis[i*prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}

void mul(int x)
{
	for(int i=1;1ll*prime[i]*prime[i]<=1ll*x&&i<=cnt;i++)
	{
		while(x % prime[i] == 0)
		{
			x /= prime[i];
			a[prime[i]]++;
		}
	}
	if(x != 1) a[x]++;
}

void div(int x)
{
	for(int i=1;1ll*prime[i]*prime[i]<=1ll*x&&i<=cnt;i++)
	{
		while(x % prime[i] == 0)
		{
			x /= prime[i];
			a[prime[i]]--;
		}
	}
	if(x != 1) a[x]--;
}

void cal(int x)
{
	int i;
	for(i=1;i<=len;i++) p[i] *= x;
	i = 1;
	while(i <= len || p[i] >= 10)
	{
		p[i + 1] += p[i] / 10;
		p[i] %= 10;
		i++;
	}
	len = i;
	while(!p[len]) len--;
}

int main()
{
	int T = 1;
	//scanf("%d",&T);
	while(T--)
	{
		len = 1;
		p[1] = 1;
		Prime(N);
		scanf("%d%d",&n,&m);
		for(int i=1;i<=min(n, m);i++) mul(n + m - i + 1);
		for(int i=1;i<=min(n, m);i++) div(i);
		for(int i=1;i<=n+m;i++)
		{
			if(a[i] == 0) continue;
			for(int j=1;j<=a[i];j++)
			{
				cal(i);
			}
		}
		for(int i=100;i>=1;i--)
		{
			printf("%d",p[i]);
			if(i % 10 == 1) printf("\n");
		}
	}
	return 0;
}
/*
50000 5000

*/
上一篇:P5736 质数筛


下一篇:三次函数