fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5.  
  6. /// O(SQRT(min(N,M))
  7. int gcd_slow(int n, int m) {
  8.   if (n > m) {
  9.     swap(n, m);
  10.   }
  11.   int gcd = 1;
  12.   for (int i = 1, dv; i * i <= n; ++i) {
  13.     dv = i;
  14.     if (n % dv == 0 and m % dv == 0) {
  15.       gcd = max(gcd, i);
  16.     }
  17.     dv = n / i;
  18.     if (n % i == 0 and m % dv == 0) {
  19.       gcd = max(gcd, dv);
  20.     }
  21.   }
  22.   return gcd;
  23. }
  24.  
  25. /// O(log(min(n,m))
  26. int gcd(int a, int b) {
  27.   if (b == 0) {
  28.     return a;
  29.   }
  30.   return gcd(b, a % b);
  31. }
  32.  
  33. int fast_power(int base, int expo) { // log(expo)
  34.   if (expo == 0) {
  35.     return 1;
  36.   }
  37.   if (expo & 1) {
  38.     return base * fast_power(base, expo - 1);
  39.   }
  40.   int res = fast_power(base, expo / 2);
  41.   res *= res;
  42.   return res;
  43. }
  44.  
  45.  
  46. const int mod = 1e9 + 7;
  47.  
  48. int binary_power(int base, int expo) { // log(expo)
  49.   int res = 1;
  50.   while (expo) {
  51.     if (expo & 1) {
  52.       res = res * base % mod;
  53.     }
  54.     base = base * base % mod;
  55.     expo >>= 1;
  56.   }
  57.   return res;
  58. }
  59.  
  60. int add(int a, int b) {
  61.   return (a % mod + b % mod) % mod;
  62. }
  63.  
  64. int sub(int a, int b) {
  65.   return (a % mod - b % mod + mod) % mod;
  66. }
  67.  
  68. int mul(int a, int b) {
  69.   return a % mod * (b % mod) % mod;
  70. }
  71.  
  72. int dv(int a, int b) {
  73.   return mul(a, binary_power(b, mod - 2));
  74. }
  75.  
  76. vector<int> inv, fact;
  77.  
  78. void build(int N) {
  79.   inv.assign(N + 1, 1);
  80.   fact.assign(N + 1, 1);
  81.   for (int i = 2; i <= N; ++i) {
  82.     fact[i] = mul(fact[i - 1], i);
  83.     inv[i] = binary_power(fact[i], mod - 2);
  84.   }
  85. }
  86.  
  87. int ncr(int n, int r) {
  88.   if (r > n)return 0;
  89.   return mul(fact[n], mul(inv[r], inv[n - r]));
  90. }
  91.  
  92. int npr(int n, int r) {
  93.   if (r > n)return 0;
  94.   return mul(fact[n], inv[n - r]);
  95. }
  96.  
  97. int32_t main() {
  98.   ios_base::sync_with_stdio(false);
  99.   cin.tie(nullptr);
  100.   build(1e6);
  101.   return 0;
  102. }
Success #stdin #stdout 0.13s 18928KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7q2lIO
language:
C++14 (gcc 8.3)
created:
12 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!