fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define maxN 10000001
  4. #define mod1 186583                     //186583*587117 = 109546051211
  5. #define mod2 587117
  6.  
  7.  
  8. using namespace std;
  9. ll fact1[maxN];
  10. ll fact2[maxN];
  11.  
  12.  
  13. ll power(ll base,ll expo, ll mod)       //fast exponentiation
  14. {
  15.     ll ans=1;
  16.     while(expo)
  17.     {
  18.         if(expo&1)
  19.             ans=(ans*base)%mod;
  20.         expo/=2;
  21.         base=(base*base)%mod;
  22.     }
  23.     return ans;
  24. }
  25.  
  26.  
  27. ll inv(ll x,ll m)               //calculating inverse using fermat's little theorem
  28. {
  29.     return(power(x,m-2,m));
  30. }
  31.  
  32.  
  33. int main()
  34. {
  35.     fact1[0]=fact1[1]=fact2[0]=fact2[1]=1;
  36.  
  37.     for(ll i=2;i<587117;i++)                   //precomputing factorials till 587117 as after that the factorials will be divisible by 109546051211
  38.     {
  39.         fact1[i]=(i*fact1[i-1])%mod1;
  40.         fact2[i]=(i*fact2[i-1])%mod2;
  41.     }
  42.  
  43.     ll n;
  44.     cin>>n;
  45.  
  46.     if(n>=587117)                       //if n>=587117 then ans will always be 0
  47.     {
  48.         cout<<0<<endl;
  49.         return 0;
  50.     }
  51.  
  52.     ll r1=1,r2=1;
  53.  
  54.     for(ll i=2;i<=n;i++)
  55.     {
  56.         r1=(r1*fact1[i])%mod1;          //calculating remainder under 186583
  57.         r2=(r2*fact2[i])%mod2;          //calculating remainder under 587117
  58.     }
  59.  
  60.     ll res=0;
  61.  
  62.     res+=(((mod2*inv(mod2,mod1))%mod1)*r1)%mod1;        // applying CRT formula (prod/a[i])*inv(prod/a[i])*remainder
  63.     res+=(((mod1*inv(mod1,mod2))%mod2)*r2)%mod2;        //applying CRT formula (prod/a[i])*inv(prod/a[i])*remainder
  64.  
  65.     cout<<(res)<<endl;
  66. }
  67.  
Success #stdin #stdout 0.01s 12744KB
comments (?)
stdin
copy 
5
stdout
copy 
69120
https://ideone.com/hmG0dO
language:
C++14 (gcc 8.3)
created:
3 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!