fork download
copy 
  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. const int m = 100000007;
  5. static int c[m];
  6.  
  7. long inv(long a)
  8. {
  9.   long z = 1;
  10.   for (long c, q, x, y = 0, b = m; b != 0; z = y, y = x)
  11.     c = a - (q = a/b) * b, a = b, b = c, x = z - q*y;
  12.   return (z < 0) ? (z + m) : z;
  13. }
  14.  
  15. long b(long n, long k)
  16. {
  17.   if (n < k) return 0;
  18.   if (n >= m) return b(n / m, k / m) * b(n % m, k % m) % m;
  19.   return inv((long)c[k] * c[n-k]) * c[n] % m;
  20. }
  21.  
  22. long f(long n)
  23. {
  24.   long z = n % m;
  25.   return (8 * b(n+n, n) - 7 - z - z - 3 * z * z) % m;
  26. }
  27.  
  28. int main()
  29. {
  30.   long z;
  31.   auto st = time(NULL);
  32.   for (int q = 0; q < 10; q++)
  33.   {
  34.     c[0] = 1;
  35.     for (long i = 1; i < m; i++) c[i] = i * c[i-1] % m;
  36.     long v, a = 0, b = 1; z = 0;
  37.     for (int i = 2; i <= 90; ++i, a = b, b = v)
  38.       z = (z + f(v = a + b)) % m;
  39.   }
  40.   auto et = time(NULL);
  41.   printf("%ld  %f ms\n", (z < 0) ? (z + m) : z, difftime(et, st)/10.0);
  42. }
Success #stdin #stdout 3.81s 392680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
89539872  0.400000 ms
https://ideone.com/eZ5QKn
Project Euler 554
language:
C (clang 8.0)
created:
19 hours 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!