fork(3) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. using i64 = long long;
  5. using u32 = unsigned;
  6. using u64 = unsigned long long;
  7.  
  8. /*
  9. // 1 でも動作する
  10. struct FastDiv {
  11.   FastDiv() {}
  12.   FastDiv(u64 n) : m(n) {
  13.     s = (n == 1) ? 0 : 64 + std::__lg(n - 1);
  14.     x = ((__uint128_t(1) << s) + n - 1) / n;
  15.   }
  16.   friend u64 operator / (u64 n, FastDiv d) { return __uint128_t(n) * d.x >> d.s; }
  17.   friend u64 operator % (u64 n, FastDiv d) { return n - n / d * d.m; }
  18.   u64 m, x; int s;
  19. };
  20. */
  21.  
  22. // 1 は動作しない
  23. struct FastDiv {
  24.   FastDiv() {}
  25.   FastDiv(u64 n) : m(n) {
  26.     s = std::__lg(n - 1);
  27.     x = ((__uint128_t(1) << (s + 64)) + n - 1) / n;
  28.   }
  29.   friend u64 operator / (u64 n, FastDiv d) { 
  30.     return (__uint128_t(n) * d.x >> d.s) >> 64; 
  31.   }
  32.   friend u64 operator % (u64 n, FastDiv d) { return n - n / d * d.m; }
  33.   u64 m, x; int s;
  34. };
  35.  
  36. inline u64 mod64_32_small(u64 a, u32 b) {
  37.   u32 q, r;
  38.   __asm__ (
  39.     "divl\t%4"
  40.     : "=a"(q), "=d"(r)
  41.     : "0"(u32(a)), "1"(u32(a >> 32)), "rm"(b)
  42.   );
  43.   return r;
  44. }
  45.  
  46. int fact_slow(int n, int mod) {
  47.   int ret = 1;
  48.   for (int i = 1; i <= n; ++i) ret = i64(ret) * i % mod;
  49.   return ret;
  50. }
  51.  
  52. int fact_slow_asm(int n, int mod) {
  53.   int ret = 1;
  54.   for (int i = 1; i <= n; ++i) ret = mod64_32_small(u64(ret) * i, mod);
  55.   return ret;
  56. }
  57.  
  58. int fact_fast(int n, int mod) {
  59.   auto fd = FastDiv(mod);
  60.   int ret = 1;
  61.   for (int i = 1; i <= n; ++i) ret = i64(ret) * i % fd;
  62.   return ret;
  63. }
  64.  
  65. int main() {
  66.   int mod; scanf("%d", &mod);
  67.   clock_t beg = clock();
  68.   int a1 = fact_slow(mod - 1, mod);
  69.   clock_t t1 = clock();
  70.   int a2 = fact_slow_asm(mod - 1, mod);
  71.   clock_t t2 = clock();
  72.   int a3 = fact_fast(mod - 1, mod);
  73.   clock_t t3 = clock();
  74.   printf("%d %.3f\n", a1, double(t1 - beg) / CLOCKS_PER_SEC);
  75.   printf("%d %.3f\n", a2, double(t2 - t1) / CLOCKS_PER_SEC);
  76.   printf("%d %.3f\n", a3, double(t3 - t2) / CLOCKS_PER_SEC);
  77.   return 0;
  78. }
Success #stdin #stdout 2.7s 15240KB
comments (?)
stdin
copy 
100000007
stdout
copy 
100000006 1.332
100000006 0.933
100000006 0.435
https://ideone.com/dpkoJW
language:
C++14 (gcc 8.3)
created:
6 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!