fork(4) download 
  1. #include<stdio.h>
  2. #define MOD 109546051211
  3. #define MOD1 186583//factors of MOD
  4. #define MOD2 587117//factors of MOD
  5. /*"call" function calculates the multiplicative inverse using Fermat's Little Theorem*/
  6. unsigned long long int call(unsigned long long int a,unsigned long long int b,int mod)
  7. {
  8.     unsigned long long int res;
  9.     if(b==1)
  10.         return a;
  11.     res=call(a,b/2,mod);
  12.     res=(res*res)%mod;
  13.     if(b%2)
  14.     res=(res*a)%mod;
  15.     return res;
  16. }
  17. int main()
  18. {
  19.     long long int i,fact,prod,n,p,q,i_eff,fact_eff,a=1,b=1;
  20.     scanf("%lld",&n);
  21.     fact=1;prod=1;i=1;
  22.     p=call(MOD1,MOD2-2,MOD2);//calculate inverse of MOD1 in MOD2
  23.     q=call(MOD2,MOD1-2,MOD1);//calculate inverse of MOD2 in MOD1
  24.     for(i=1;i<=n;i++)
  25.     {
  26.         a=i%MOD1;b=i%MOD2;
  27.         i_eff=(a*MOD2*q+b*MOD1*p)%MOD;//calculates i%MOD
  28.         fact*=i_eff;
  29.         a=fact%MOD1;b=fact%MOD2;
  30.         fact_eff=(a*MOD2*q+b*MOD1*p)%MOD;//calculates fact%MOD
  31.         prod*=(fact_eff);
  32.         a=prod%MOD1;b=prod%MOD2;
  33.         prod=(a*MOD2*q+b*MOD1*p)%MOD;//calculates prod%MOD
  34.         }
  35.     printf("%lld\n",prod);
  36.     return 0;
  37.     }
Success #stdin #stdout 0s 2296KB
comments (?)
stdin 
5
stdout 
34560
https://ideone.com/U97WEX
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!