fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long mod = 1e9 + 7;
  4. int mu[40005]; // mu[i] = x --> i^j với j = x;
  5.  
  6. long long POW(long long a, long long b){ // tinh (a^b) % mod
  7.      if(b == 0) return 1;
  8.      if(b == 1) return a;
  9.      long long t = POW(a, b / 2);
  10.      if(b % 2 == 0) return t * t % mod;
  11.      return t * t % mod * a % mod;
  12. }
  13. int main()
  14. {
  15.      ios_base::sync_with_stdio(0);
  16.      cout.tie(0); cin.tie(0);
  17.      freopen("test.inp", "r", stdin);
  18.      freopen("test.out", "w", stdout);
  19.      int n; cin >> n;
  20.      // mu[2] = 1 --> 2^1
  21.      // khi * 4 vao 3! --> mu[2] = 3
  22.      // 4! = 2 * 3 * 4 = 2^3 * 3^1 --> mu[2] = 3; mu[3] = 1
  23.      // 5! --> mu[2] = 3; mu[3] = 1; mu[5] = 1
  24.      for(int num = 2; num <= n; num++){
  25.           int temp = num;
  26.           for(int i = 2; i * i <= temp; i++){
  27.                while(temp % i == 0){
  28.                     mu[i]++;
  29.                     temp /= i;
  30.                }
  31.           }
  32.           if(temp != 1) mu[temp]++;
  33.      }
  34.  
  35.      long long res = 1;
  36.      for(int num = 2; num <= n; num++){
  37.           bool ok = true;
  38.           for(int i = 2; i * i <= num; i++){
  39.                if(num % i == 0){
  40.                     ok = false;
  41.                     break;
  42.                }
  43.           }
  44.  
  45.           if(ok){
  46.                if(mu[num] % 2 == 1){
  47.                     mu[num]--;
  48.                }
  49.                res = (res * POW(num, mu[num])) % mod;
  50. //               cout << num << " " << mu[num] << '\n';
  51.           }
  52.      }
  53.      cout << res;
  54.  
  55. }
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
Success #stdin #stdout 0s 5252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CJk4vX
language:
C++14 (clang 8.0)
created:
9 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!