fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 1e6;
  5. const int mod = 1e9 + 7;
  6. int S[N + 1];
  7. int n, x, t;
  8. int cnt[N + 1];
  9.  
  10. int Pow(int a, int b)
  11. {
  12.     int res(1);
  13.     while (b)
  14.     {
  15.         if (b & 1)
  16.             res = (res * a) % mod;
  17.         a = (a * a) % mod;
  18.         b >>= 1;
  19.     }
  20.     return res;
  21. }
  22.  
  23. signed main()
  24. {
  25.     ios_base::sync_with_stdio(0);
  26.     cin.tie(0);
  27.  
  28.     for (int i(2); i <= N; i++)
  29.         if (!S[i])
  30.         {
  31.             S[i] = i;
  32.             for (int j(i * i); j <= N; j += i)
  33.                 if (!S[j])
  34.                     S[j] = i;
  35.         }
  36.  
  37.     cin >> n;
  38.     while (n--)
  39.     {
  40.         cin >> t;
  41.         while (t > 1)
  42.         {
  43.             cnt[S[t]]++;
  44.             t /= S[t];
  45.         }
  46.     }
  47.  
  48.     cin >> x;
  49.     int res(1);
  50.     for (int i(1); i <= N; i++)
  51.         if (cnt[i])
  52.         {
  53.             int t = cnt[i];
  54.             res = ((res * (Pow(i, t * x + 1) - 1)) % mod * Pow(i - 1, mod - 2) % mod) % mod;
  55.         }
  56.  
  57.     cout << res;
  58.  
  59.     return 0;
  60. }
Success #stdin #stdout 0.01s 11948KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/p8c84f
language:
C++14 (gcc 8.3)
created:
1 year 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!