Blog·Tanky WooABOUTRSS

HDU/HDOJ 1042 N!(大数乘法)

04 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1042

最基本的大数乘法题目,我曾经写过一个大数乘整数的模板:http://www.wutianqi.com/?p=917

这里直接套用了,也就顺便验证了其可靠性。

AC代码:

#include
#include 
using namespace std;

char a[100005], s[100005];
int b;

int m[100005], p[100005];
// 大数乘小数
// 大数a乘以小数b,结果返回给s
void big_Mult_small(char a[], int b, char s[])
{
    // 初始化
    memset(m, 0, sizeof(m));
    memset(p, 0, sizeof(p));
    int len = strlen(a);
    // 把a逆序赋给m整形数组
    for(int i=0; i=10)
        {
            p[i+1] += p[i]/10;
            p[i] = p[i]%10;
        }
    while(p[len])
    {
        if(p[len]>=10)
        {
            p[len+1] += p[len]/10;
            p[len] = p[len]%10;
        }
        len++;
    }
    for(int i=0; i> n)
    {
        if(n == 0 || n == 1)
        {
            cout << 1 << endl;
            continue;
        }
        memset(a, 0, sizeof(a));
        memset(s, 0, sizeof(s));
        a[0] = '1';
        for(int i=2; i<=n; ++i)
        {
            big_Mult_small(a, i, s);
            strcpy(a, s);
        }
        for(int i=0; i<strlen(s); ++i)
            printf("%c", s[i]);
        printf("\n");
    }
}