fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.   int n;
  7.   cin >> n;
  8.   const int md = 1e8 + 7;
  9.   auto mul = [&](int a, int b) {
  10.     return (long long) a * b % md;
  11.   };
  12.   auto power = [&](int a, int e) {
  13.     int ret = 1;
  14.     for (; e; e >>= 1) {
  15.       if (e & 1) {
  16.         ret = mul(ret, a);
  17.       }
  18.       a = mul(a, a);
  19.     }
  20.     return ret;
  21.   };
  22.   vector<bool> p(n + 1, true);
  23.   int ans = 1;
  24.   for (int i = 2; i <= n; i++) {
  25.     if (!p[i]) {
  26.       continue;
  27.     }
  28.     int cnt = 0;
  29.     for (long long ipow = i; ipow <= n; ipow *= i) {
  30.       cnt += n / ipow;
  31.     }
  32.     if (cnt & 1) {
  33.       cnt--;
  34.     }
  35.     ans = mul(ans, power(i, cnt));
  36.     if ((long long) i * i > n) {
  37.       continue;
  38.     }
  39.     for (int j = i * i; j <= n; j += i) {
  40.       p[j] = false;
  41.     }
  42.   }
  43.   cout << ans << '\n';
  44.   cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
  45.   return 0;
  46. }
  47.  
Success #stdin #stdout #stderr 0.02s 4400KB
comments (?)
stdin 
1926817
stdout 
95487326
stderr 
Time: 0.024663
https://ideone.com/TPk2aR
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!