HDOJ 2674-N！Again【数论】

港控/mmm° 2022-08-18 02:07 75阅读 0赞

# N！Again #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 4266 Accepted Submission(s): 2278**

Problem Description

WhereIsHeroFrom: Zty, what are you doing ?  
Zty: I want to calculate N!......  
WhereIsHeroFrom: So easy! How big N is ?  
Zty: 1 <=N <=1000000000000000000000000000000000000000000000…  
WhereIsHeroFrom: Oh! You must be crazy! Are you Fa Shao?  
Zty: No. I haven's finished my saying. I just said I want to calculate N! mod 2009  
  
  
Hint : 0! = 1, N! = N\*(N-1)!

Input

Each line will contain one integer N(0 <= N<=10^9). Process to end of file.

Output

For each case, output N! mod 2009

Sample Input

4 
    5

Sample Output

24
    120

Author

WhereIsHeroFrom

Source

[HDU女生专场公开赛——谁说女子不如男][HDU]

解题思路

根据阶乘的性质我们可以知道当阶乘数超过2009时，阶乘最后对2009取余时都等于0。另外注意for循环的结果都要对2009取余，否则有可能溢出。

#include<stdio.h>
    int main()
    {
    	int a;
    	while(scanf("%d",&a)!=EOF)
    	{
    		int s=1;
    		if(a>2009)
    		{
    			printf("0\n");
    		}
    		else
    		{
    			for(int i=1;i<=a;i++)
    			{
    				s*=i;
    				s=s%2009;
    			}
    			printf("%d\n",s);
    		}
    		
    	}
    	return 0;
    }

[HDU]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU%C5%AE%C9%FA%D7%A8%B3%A1%B9%AB%BF%AA%C8%FC%A1%AA%A1%AA%CB%AD%CB%B5%C5%AE%D7%D3%B2%BB%C8%E7%C4%D0&source=1&searchmode=source

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关数论集训

我们知道，在编程中，我们时常需要考虑到时间复杂度，特别是对于循环的部分。例如，如果代码中出现 for(i=1;i<=n;i++) OP ; 那么做了n次OP运算，

墨蓝/ 2024年02月18日 22:22/ 0 赞/ 10 阅读

相关 HDU 2674 D - N！Again

Problem Description WhereIsHeroFrom: Zty, what are you doing ? Zty: I want to calcul

待我称王封你为后i/ 2022年12月17日 15:00/ 0 赞/ 126 阅读

相关数论-素数

文章目录判断素数筛法求素数例题 HDU-1262 HDU-3792 判断素数 -----------------

女爷i/ 2022年11月27日 12:22/ 0 赞/ 193 阅读

相关 HDOJ 2674-N！Again【数论】

N！Again Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/

港控/mmm°/ 2022年08月18日 02:07/ 0 赞/ 76 阅读

相关 2674 3-5 学生成绩统计

[3-5 学生成绩统计][3-5] include<iostream> include<cmath> include<iomanip> usi

蔚落/ 2022年07月15日 03:40/ 0 赞/ 110 阅读

相关【数论】c

c 【题目描述】给定一个正整数n，在\[1,n\]的范围内，求出有多少个无序数对(a,b)满足gcd(a,b)=a xor b。【输入格式】输入共一行，一

男娘i/ 2022年06月06日 04:44/ 0 赞/ 199 阅读

相关 2674 3-5 学生成绩统计

3-5 学生成绩统计 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 通过本题目练习可

骑猪看日落/ 2022年06月05日 05:53/ 0 赞/ 173 阅读

相关数论基础

数论质数筛选素数筛 //复杂度（NlogN） for (int i = 2; i <= n; ++i) { is_prim

男娘i/ 2022年02月04日 09:11/ 0 赞/ 345 阅读

相关数论基础

前言：一些比较基础的数论知识正文： GCD $gcd$ 的求法当然要用欧几里得定理，就是辗转相除 int gcd(int a,int b) {

约定不等于承诺〃/ 2021年12月16日 04:36/ 0 赞/ 307 阅读

相关数论——素数

转自：[http://www.cnblogs.com/linyujun/p/5198832.html][http_www.cnblogs.com_linyujun_p_5198

向右看齐/ 2021年11月01日 06:16/ 0 赞/ 362 阅读