本文主要是介绍hdu 2674(想法+数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题要计算的是N!%2009，0<=N<=10^9。
思路：从1开始累乘，直到乘到因子为N为止，并且在相乘过程中，每相乘一次都mod2009，这样做和把所有1---N因子都乘完后再
mod2009结果是一样的。原因在于每个数都能分为除以2009后的商部分和余数部分。用这个数乘以n，和用这个数除以2009的商乘
以n以及余数乘以n，效果完全一样。商乘以n的部分任然是下一个数商部分；而余数乘以n的部分如果大于2009，则再mod2009，
而余数除以2009的值再加上之前说过的商乘以n则就是这个数的除以2009的商了。
任意自然数n=(n/2009)*2009+(n%2009)
当然，仅仅的暴力计算必然会TLE，N最大为10^9！
找规律吧。N>=41的结果都为0。因为N=40，结果为245，N=41时，结果为245*41=10045%2009=0。任何不小于41的n都得是
(((((0*42)%2009)*43)%2009)*44)%2009...结果显然为0了。
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#define mod 2009
using namespace std;
int main()
{int n,ans;while(scanf("%d",&n)!=EOF){ans=1;if(n>40)printf("0\n");else{for(int i=1; i<=n; i++){ans=(ans*i)%mod;}printf("%d\n",ans);}}return 0;
}
这篇关于hdu 2674(想法+数学)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
