首页 > 代码库 > HDU -2674 N！Again(小技巧)
HDU -2674 N！Again(小技巧)
这道题有个小技巧，就是既然是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 else22 printf("%d\n", dp[n]);23 }24 return 0;25 }
HDU -2674 N！Again(小技巧)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。