hdoj 2647 N!Again
2024-10-14 11:56:51
N!Again
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4016 Accepted Submission(s):
2157
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
?
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.
N<=10^9). Process to end of file.
Output
For each case, output N! mod 2009
Sample Input
4
5
Sample Output
24
120
此题仍然用同余定理:前边文章中已经做出详细解释这里就不解释了
此题还有一个技巧就是41(包括41)之后的所有数据结果都是0
因为40求出的结果是245==49*5 2009==49*41
下一步对41求阶乘并对2009取模就等于(41%2009*245%2009)%2009==(41*245)%2009==0
所以之后的每一步都等0
AC代码:
#include<stdio.h>
#include<string.h>
int main()
{
int n,m,j,i,s,t;
while(scanf("%d",&n)!=EOF)
{
if(n>=41)
printf("0\n");
else
{
s=1;
for(i=2;i<=n;i++)
{
s=s%2009*i%2009;
s=s%2009;
}
printf("%d\n",s);
}
}
return 0;
}
最新文章
- Serif和Sans-serif字体的区别
- Hibernate整合C3P0实现连接池
- Navicat For Mysql快捷键
- Android应用签名
- mkfs 的使用
- 一个页面从输入URL到页面加载显示完成的详细过程
- Windows下安装虚拟机和Linux
- 移动端JS事件、移动端框架
- JPG .vs. PNG
- 静态编译程序 依赖于 Qt 和 Opencv 静态库 会出现 jpeg jpg 图像格式保存崩溃的情况,这是什么原因?
- C# 利用位运算传递多个参数方法
- vue原理20181211
- Window上安装—Docker 笔记
- shell脚本:Kill掉MySQL中所有sleep的client线程
- 解决Oracle登录极慢的问题
- 用 C# 编写 NEO 智能合约
- Java的map键值对的用法,map的遍历,Entry对象的使用
- allegro中如何添加安装孔(注:在PCB图纸中添加)
- Alpha冲刺-第一天
- 后端利用Redis队列及哈希实现定时推送提醒的三个思路