fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mod 1000000007
  5.  
  6. ll gcdExtended(ll a, ll b, ll *x, ll *y);
  7.  
  8. // Function to find modulo inverse of b. It returns
  9. // -1 when inverse doesn't
  10. ll modInverse(ll b, ll m)
  11. {
  12.     ll x, y; // used in extended GCD algorithm
  13.     ll g = gcdExtended(b, m, &x, &y);
  14.  
  15.     // Return -1 if b and m are not co-prime
  16.     if (g != 1)
  17.         return -1;
  18.  
  19.     // m is added to handle negative x
  20.     return (x % m + m) % m;
  21. }
  22.  
  23. // Function to compute a/b under modulo m
  24. void modDivide(ll a, ll b, ll m)
  25. {
  26.     a = a % m;
  27.     ll inv = modInverse(b, m);
  28.     if (inv == -1)
  29.         cout << "Division not defined";
  30.     else
  31.         cout << (inv * a) % m;
  32. }
  33.  
  34. // C function for extended Euclidean Algorithm (used to
  35. // find modular inverse.
  36. ll gcdExtended(ll a, ll b, ll *x, ll *y)
  37. {
  38.     // Base Case
  39.     if (a == 0)
  40.     {
  41.         *x = 0, *y = 1;
  42.         return b;
  43.     }
  44.  
  45.     ll x1, y1; // To store results of recursive call
  46.     ll gcd = gcdExtended(b % a, a, &x1, &y1);
  47.  
  48.     // Update x and y using results of recursive
  49.     // call
  50.     *x = y1 - (b / a) * x1;
  51.     *y = x1;
  52.  
  53.     return gcd;
  54. }
  55.  
  56. int main()
  57. {
  58.  
  59.     cin.tie(NULL);
  60.     cout.tie(NULL);
  61.  
  62.     ll fac[1000000 + 1];
  63.     fac[0] = 1;
  64.     for (ll i = 1; i <= 1000000; i++)
  65.     {
  66.         fac[i] = (fac[i - 1] * i) % mod;
  67.     }
  68.     ll t;
  69.     cin >> t;
  70.  
  71.     while (t--)
  72.     {
  73.         ll a, b;
  74.         cin >> a >> b;
  75.  
  76.         modDivide(fac[a], (fac[b] * fac[a - b]) % mod, mod);
  77.  
  78.         cout << endl;
  79.     }
  80. }
Success #stdin #stdout 0.01s 11316KB
comments (?)
stdin
copy 
3
5 3
8 1
9 5
stdout
copy 
10
8
126
https://ideone.com/vwWpsu
language:
C++14 (clang 8.0)
created:
1 year 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!