fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. int mod, np;
  6. long long p[32010];
  7.  
  8. class Powerit
  9. {
  10. public:
  11.     Powerit(){}
  12.     long long mul(long long x, long long k)
  13.     {
  14.         if (k == 1) return x;
  15.         long long kk = mul(x, k/2);
  16.         if (k % 2 == 0)
  17.             return ((kk * kk) % mod);
  18.         else
  19.            return ((((kk * kk) % mod) * x) % mod);
  20.     }
  21.  
  22.     int calc(int n, int k, int m)
  23.     {
  24.         mod = m;
  25.         int cp = m;
  26.         // EFT with m
  27.         int x = 2;
  28.         while (x * x <= cp) {
  29.             long long kk = 1;
  30.             while (m % x == 0)
  31.             {
  32.                 kk*=x;
  33.                 m = m/x;
  34.             }
  35.             if (kk > 1)
  36.             {
  37.                 kk = (kk / x)*(x - 1);
  38.                 np++;
  39.                 p[np] = kk;
  40.             }
  41.             x++;
  42.         }
  43.         if (m > 1)
  44.         {
  45.             np++;
  46.             p[np] = m;
  47.         }
  48.         m = cp;
  49.         long long kk = 1;
  50.         for (int i = 1; i <= np; i++)
  51.              kk *= p[i];
  52.  
  53.         // 2^k - 1
  54.         long long mu = 1;
  55.         for (int i = 1; i <= k; i++)
  56.             mu = (mu * 2) % kk;
  57.         mu = (mu - 1) % kk;
  58.         //
  59.         long long sum = 0;
  60.         for (int i = 1; i <= n; i++)
  61.         {
  62.             sum = (sum + mul(i % mod, mu)) % mod;
  63.         }
  64.         return sum;
  65.     }
  66. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/4.9/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/V31FsJ
language:
C++14 (gcc 8.3)
created:
9 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!