fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1234567891;
  5.  
  6. long long modPow(long long x, long long y, int MOD) {
  7.     long long res = 1;
  8.     x = x % MOD;
  9.     while (y > 0) {
  10.         if (y & 1) res = (res * x) % MOD;
  11.         y = y >> 1;
  12.         x = (x * x) % MOD;
  13.     }
  14.     return res;
  15. }
  16.  
  17. int main() {
  18.     int n;
  19.     cin >> n;
  20.  
  21.     vector<bool> prime(n + 1, true);
  22.     vector<int> primes;
  23.  
  24.     for (int p = 2; p * p <= n; ++p) {
  25.         if (prime[p]) {
  26.             for (int i = p * p; i <= n; i += p)
  27.                 prime[i] = false;
  28.         }
  29.     }
  30.  
  31.     for (int p = 2; p <= n; ++p) {
  32.         if (prime[p]) {
  33.             primes.push_back(p);
  34.         }
  35.     }
  36.  
  37.     long long result = 1;
  38.     for (int p : primes) {
  39.         long long count = 0;
  40.         for (long long pw = p; pw <= n; pw *= p) {
  41.             count += n / pw;
  42.         }
  43.  
  44.         count -= count % 2;
  45.         result = (result * modPow(p, count, MOD)) % MOD;
  46.     }
  47.  
  48.     cout << result << endl;
  49.  
  50.     return 0;
  51. }
  52.  
Runtime error #stdin #stdout #stderr 0.01s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/0V4mEt
language:
C++14 (gcc 8.3)
created:
233 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!