问题 E: 猩猩散步

链接：http://acm.ocrosoft.com/problem.php?cid=2001&pid=4

题目描述

　　猩猩，骆驼，还有泡泡经常喜欢在饭后到操场上散步，由于猩猩的走路姿势最突出最显眼，理所应当的成为他们中的主角，所以我的题目就说猩猩散步了。（骆驼和泡泡别有意见哈，和猩猩争啥……）　　当然，话说回来，猩猩在OI上的能力也是不容低估的，你看，散步时还会想一道与此相关的问题，这是道经典的不能再经典的问题了。　　在一个m×n的矩阵上，猩猩在左下角的顶点出现了，他只能沿着路径向上或者向右走，他的目标是“蠕动”到右上角的顶点，问他有多少路径可以选择。嗯，这个、这个、这个似乎地球人都知道怎么做，但是请注意，我有个条件没给呢！m和n现在的最大范围是50000，这可怎么办？仔细想想吧。

输入

只有一行，包含两个整数m和n，其上限均为50000

输出

由于最后的答案数目过大，所以只检查后100位，输出时每行十个数字，没空格间隔，共十行，如果答案位数没超过100位，则需要在空位上补0。

样例输入

7 4

样例输出

题解：就是简单的求c(n,n+m)的问题，主要还是看大数的处理，普通的大数会被卡（不知道为什么，可能是常数的问题），这里用到了素数大数乘，比如样例求C（4,11）=11×10×9×8÷4÷3÷2÷1

可以转化成(11^1)×(2^1×5^1)×(3^2)×(2^3)÷(2^2)÷(3^1)÷(2^1)

题解：

#include<bits/stdc++.h>
using namespace std;
long long x,k,ans=1,s=0,l=0;
int a[100005];
bool prime[100005];
int p[1000005];
void mu(int q) 
{
    for(int i=1;i<=l;i++)
    p[i]=p[i]*q;
    int i=1;
    while(i<=l||p[i]>10)
    {
        p[i+1]=p[i+1]+p[i]/10;
        p[i]=p[i]%10;
        i++;
    }
    l=i;
    while(!p[l]) 
	l--;
}
void mu2(int q)
{
    for(int i=1;i<=sqrt(q)+1;i++)
    { 
        if(prime[i])
        { 
            while(q%i==0)
            {
                a[i]++;
                q=q/i;
            }
        } 
    } 
    if(q>0) 
	a[q]++;
}
void di(int q)
{
    for(int i=1;i<=sqrt(q)+1;i++)
    { 
        if(prime[i])
        { 
            while(q%i==0)
            {
                a[i]--;
                q=q/i;
            }
        }
	} 
    if(q>0) 
	a[q]--;
}
int main()
{
    p[1]=1;
    l=1;
    cin>>k>>x;
    ans=k+x;
    for(int i=2;i<=ans;i++)
    prime[i]=true;
    for(int i=2;i<=ans;i++)//筛素数 
    { 
        if(prime[i])
        {
        	for (int j=i;j<=ans/i;j++)
            prime[i*j]=false;
        } 
    }
    for(int i=1;i<=min(k,x);i++)//ans*(ans-1)*……min(k,x) 
    mu2(ans-i+1);
    for(int i=1;i<=min(k,x);i++)//min(k,x)!
    di(i);
    for(int i=1;i<=ans;i++) 
    {
        for(int j=1;j<=a[i];j++)
        mu(i);
    } 
    for(int i=100;i>=1;i--)//输出 
    { 
        if(i%10!=1)//补零 
		cout<<p[i];
        else
		cout<<p[i]<<endl;
	} 
    return 0;
}