题目：

4 
5

24
120

题目分析：

             这道题，扫了一眼题目以后，再扫一遍数据规模，就知道直接暴力肯定是会超时的，因为n大的有点吓人啊。这种题，个人觉得可能还是得找规律。规律主要从以下两个方面找：

1）可能存在循环节。如果存在循环节，吧循环节找到(假设是m)，那么输入n的时候，输出fac(n%m)即可。

2）可能某一项(假设是m)以后%2009以后的结果全是一个数k。那么就只需要计算前m项即可，当n>m时，直接输出相应结果就行。

为了确定是以上两种情况的哪一种，我写了一下的java打表程序(因为n为41是，阶乘的结果就是33452526613163807108170062053440751665152000000000了，这已经超出了证书的范围，所以需要用到java中的大数)。直达前100项，个人觉得前100项一般都能说明问题了。

在这里需要注意一点的是：

1*2*3.。。*i%2009所得到的结果与1%2009*2%2009......i%2009所得到的结果是完全一样的。fac(41)阶乘已经超过long 的范围了，所以这里去一下巧，每一项都%2009,用来避免超过long 的范围

打表程序

import java.math.BigInteger;
import java.util.Scanner;


public class Test {

	public static BigInteger fac(int n){
		BigInteger sum = new BigInteger("1");
		
		
		int i;
		for(i = 1 ;  i <= n; ++i){
			sum = sum.multiply(BigInteger.valueOf(i));
		}
		
		return sum.mod(BigInteger.valueOf(2009));
//		return sum;
	}
	public static void main(String[] args) {
//		Scanner scanner = new Scanner(System.in);
//		
//		while(scanner.hasNext()){
//			int n = scanner.nextInt();
//			System.out.println(fac(n));
//		}
		
		
		int i;
		for(i = 1 ; i <= 100 ; i++){
			System.out.println(i + ": " + fac(i));
		}
	
	}
}

通过打表，确定了猜想2是符合这道题的规律。第41项以后的阶乘出来的数%2009的结果都是0。既然规律都找到了，

那么接下来就是编写代码了：

/*
 * f.cpp
 *
 *  Created on: 2015年2月2日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>

using namespace std;

long long fac(long long n){
	int i;
	long long sum = 1;
	for(i = 1 ; i <= n ; ++i){
		sum *= i;
		sum %= 2009;
	}

	return sum;
}

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		if(n < 41){
			printf("%lld\n",fac(n));
		}else{
			printf("0\n");
		}
	}

	return 0;
}

(hdu step 2.2.8)N！Again(求N!的阶乘%2009以后的结果)