51nod OJ P1008 N的阶乘 mod P

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;
}
上一篇:spring-aop的简单实例注解版


下一篇:mac电脑php+mysql+nginx+phpmyadmin环境搭建