G - N！Again 阶乘取模

2019-04-13 14:20发布

站内文章 / 模拟电子
15403 0 1644
G - N！Again Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status 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

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,m,n) for(i=m;i<=n;i++) #define rsp(it,s) for(set::iterator it=s.begin();it!=s.end();it++) #define mod 2009 #define inf 0x3f3f3f3f #define vi vector #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair #define Lson L, mid, rt<<1 #define Rson mid+1, R, rt<<1|1 const int maxn=5e2+10; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} ll n ; int main() { while(scanf("%d",&n)==1) { if(n>40) { printf("0 "); continue; } ll re=1; for(int i=1;i<=n;i++) re = ((re%mod)*(i%mod))%mod; printf("%lld ",re); } return 0; }



热门文章