fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. // Function to compute factorial modulo M
  8. ll factorial_mod(ll n, ll M) {
  9.     ll res = 1;
  10.     for (ll i = 2; i <= n; ++i)
  11.         res = (res * i) % M;
  12.     return res;
  13. }
  14.  
  15. // Function to compute power modulo M
  16. ll power_mod(ll base, ll exponent, ll M) {
  17.     ll result = 1;
  18.     base = base % M;
  19.     while (exponent > 0) {
  20.         if (exponent % 2 == 1)
  21.             result = (result * base) % M;
  22.         base = (base * base) % M;
  23.         exponent = exponent / 2;
  24.     }
  25.     return result;
  26. }
  27.  
  28. // Function to compute modular inverse using Fermat's Little Theorem
  29. ll mod_inverse(ll a, ll M) {
  30.     return power_mod(a, M - 2, M);
  31. }
  32.  
  33. int main() {
  34.     ll N, M;
  35.     cin >> N >> M;
  36.  
  37.     ll N_factorial = factorial_mod(N, M);
  38.     ll numerator = (N_factorial * ((N * N - 1) % M)) % M;
  39.     ll denominator = (4 * N) % M;
  40.     cout<<denominator<<endl;
  41.     // Compute modular inverse of denominator
  42.     ll denom_inv = mod_inverse(denominator, M);
  43.  
  44.     ll S = (numerator * denom_inv) % M;
  45.  
  46.     cout << S << endl;
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
3 107
stdout
copy 
12
4
https://ideone.com/UHPJiN
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

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!