这道题有个小技巧，就是既然是n!，那么对2009求余，只要大于2009!，那么一定是0，在仔细想想会发现，根本到不了2009，只要到2009的最大质因数就行了，为什么呢？因为最大质因数是最大的一个不能被2009整除的，2009的最大质因数是41，也就是只要大于41的阶乘的都可以整除2009，因为41的阶乘可以整除，42！ = 42 * 41!，所以大于41的全部为0，那么这个题就简单了
代码如下：
1 #include<iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int dp[45]; 6 int main() 7 { 8 9 dp[0] = 1; 10 dp[1] = 1; 11 dp[2] = 2; 12 for (int i = 3; i < 45; i++) 13 { 14 dp[i] = dp[i - 1] * i % 2009; 15 } 16 int n; 17 while (~scanf("%d", &n)) 18 { 19 if (n >= 41) 20 puts("0"); 21 else 22 printf("%d\n", dp[n]); 23 } 24 return 0; 25 }
原文：http://www.cnblogs.com/Howe-Young/p/4168143.html