fork(1) download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <vector>
  5. #include <stack>
  6. #include <queue>
  7. #include <set>
  8. #include <map>
  9. #include <algorithm>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <cctype>
  14. #include <cmath>
  15. #include <cassert>
  16. #include <sys/time.h>
  17. using namespace std;
  18.  
  19. #define all(c) (c).begin(), (c).end()
  20. #define iter(c) __typeof((c).begin())
  21. #define cpresent(c, e) (find(all(c), (e)) != (c).end())
  22. #define rep(i, n) for (int i = 0; i < (int)(n); i++)
  23. #define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
  24. #define pb(e) push_back(e)
  25. #define mp(a, b) make_pair(a, b)
  26.  
  27. #include <sys/time.h>
  28. #include <unistd.h>
  29. #include <stdarg.h>
  30.  
  31. struct __bench__ {
  32.   double start;
  33.   char msg[100];
  34.   __bench__(const char* format, ...)
  35.   __attribute__((format(printf, 2, 3)))
  36.   {
  37.     va_list args;
  38.     va_start(args, format);
  39.     vsnprintf(msg, sizeof(msg), format, args);
  40.     va_end(args);
  41.  
  42.     start = sec();
  43.   }
  44.   ~__bench__() {
  45.     fprintf(stderr, "%s: %.6f sec\n", msg, sec() - start);
  46.   }
  47.   double sec() {
  48.     struct timeval tv;
  49.     gettimeofday(&tv, NULL);
  50.     return tv.tv_sec + tv.tv_usec * 1e-6;
  51.   }
  52.   operator bool() { return false; }
  53. };
  54.  
  55. #define benchmark(...) if(__bench__ __b__ = __bench__(__VA_ARGS__));else
  56.  
  57.  
  58.  
  59. typedef long long ll;
  60.  
  61. namespace pow_mod {
  62. inline ll pow_mod(ll a, ll k, ll m) {
  63.   ll r = 1;
  64.   for (; k > 0; k >>= 1) {
  65.     if (k & 1) (r *= a) %= m;
  66.     (a *= a) %= m;
  67.   }
  68.   return r;
  69. }
  70.  
  71. inline ll inverse(ll a, ll m) {
  72.   return pow_mod(a, m - 2, m);
  73. }
  74. }
  75.  
  76. namespace exgcd {
  77. inline ll exgcd(ll a, ll b, ll &x, ll &y){
  78.   ll u[] = {a, 1, 0}, v[] = {b, 0, 1};
  79.   while(*v){
  80.     ll t = *u / *v;
  81.     rep(i, 3) swap(u[i] -= t * v[i], v[i]);
  82.   }
  83.   x = u[1]; y = u[2];
  84.   return u[0];
  85. }
  86. inline ll inverse(ll a, ll m){
  87.   ll p, q;
  88.   exgcd(a, m, p, q);
  89.   return (p%m+m)%m;
  90. }
  91. }
  92.  
  93.  
  94.  
  95. const ll MOD = 1000000009;
  96. const int N = 1000000;
  97.  
  98. int main() {
  99.   int a;
  100.   scanf("%d", &a);
  101.  
  102.   rep (i, 3) {
  103.     benchmark("pow_mod %d", i) {
  104.       ll t = a;
  105.       for (int k = 1; k <= N; ++k) {
  106.         t = pow_mod::inverse(t, MOD) * k % MOD;
  107.       }
  108.       printf("(%lld)\n", t);
  109.     }
  110.   }
  111.   rep (i, 3) {
  112.     benchmark("exgcd %d", i) {
  113.       ll t = a;
  114.       for (int k = 1; k <= N; ++k) {
  115.         t = exgcd::inverse(t, MOD) * k % MOD;
  116.       }
  117.       printf("(%lld)\n", t);
  118.     }
  119.   }
  120.  
  121.   return 0;
  122. }
  123.  
Success #stdin #stdout 7.85s 2684KB
comments (?)
stdin
copy 
10
stdout
copy 
(139085015)
(139085015)
(139085015)
(139085015)
(139085015)
(139085015)
https://ideone.com/lw6pfl
language:
C++ (gcc 8.3)
created:
11 years 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!