P1008 N的阶乘 mod P

OJ:51Nod

链接："http://www.51nod.com/Challenge/Problem.html#!#problemId=1008"

题目描述：

输入N和P（P为质数），求N! Mod P = ? (Mod 就是求模 %)

例如：n = 10， P = 11，10! = 3628800

3628800 % 11 = 10

输入：

两个数N,P，中间用空格隔开。(N < 10000, P < 10^9)

输出：

输出N! mod P的结果。

限制条件：

时间：1s     空间： 131072KB

输入样例：

10 11

输出样例：

10

思路：阶乘——一看就觉得很大，10！=3628800，而最大可以去10000-1......那大概是long long long long long long long long也放不了，但是看到后面对P求余，P最大是\(10^9\),也就是说答案不会大于int的范围.......这个时候就想到了每一步都求余防止溢出.......这里就要一点点数学知识了

( a * b) % c == ( ( a % c ) * b ) % c

这个公式很重要，以后还要用到，牢记

C++代码（错误的）

#include<bits/stdc++.h>

using namespace std;

int main()

{

	 int a,b,ans;

	cin>>a>>b;

	ans=1%b;

	for(int i=2;i<=a;i++)

	{

		ans=((i%b)*ans)%b;

	}

	cout<<ans;

	return 0;

}

为什么会错呢？明明什么都考虑了

然而，由于求余的结果可能会达到\(10^8\)，这个时候再乘以100就爆int的范围了

所以还是要 long long

C++代码（更正）

#include<bits/stdc++.h>

using namespace std;

int main()

{

	long long int a,b,ans;

	cin>>a>>b;

	ans=1%b;

	for(int i=2;i<=a;i++)

	{

		ans=((i%b)*ans)%b;

	}

	cout<<ans;

	return 0;

}

C代码

#include<stdio.h>

int main()

{

	long long int a,b,ans;

	scanf("%lld %lld",&a,&b);

        ans=1%b;

	for(int i=2;i<=a;i++)

	{

		ans=((i%b)*ans)%b;

	}

        printf("%d",ans);

	return 0;

}