落絮飞雁的个人网站

顺流而下,把梦做完

HDOJ:阶乘取余

一道关于递推的题目,题目链接在这里

Problem Description
来个阶乘的题,给一个不超过100000的整数N,请求出Sum=1!+2!+3!+…….+N!。如果N很大,那结果的位数会不会太多?那好,如果Sum超过6位数,只要求最后6位数,这样简单了吧
Input
每组数据包含一个整数N(1取余的时候注意前面加括号,多么痛的领悟……
代码:

#include
#include
using namespace std;
__int64 sum[100000] = { 1, 1 };
int math(int a)
{
	int j;
	__int64 cache = 1;
	for (j = 2; j <= a; j++)
	{
		cache = cache*j % 1000000;
		sum[j] = (cache + sum[j - 1]) % 1000000;
	}
	return 0;
}
int main()
{
	int i;
	while (~scanf("%d", &i))
	{
		math(i);
		printf("%I64dn", sum[i]);
	}

	return 0;
}

精简代码By郭晓磊:

#include
int main()
{
    int n,i;
    __int64 x[100005],temp;
    x[1]=temp=1;
    for(i=2;i<=100000;i++){
        temp=temp*i%1000000;
        x[i]=(x[i-1]+temp)%1000000;
    }
    while(scanf("%d",&n)!=EOF){
        printf("%I64dn",x[n]);
    }
}


原文标题:HDOJ:阶乘取余|落絮飞雁的个人网站
原文链接:https://www.luoxufeiyan.com/2015/04/09/hdoj-factorial/
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。