fork download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <cmath>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <ctime>
  8. #include <deque>
  9. #include <iostream>
  10. #include <limits>
  11. #include <numeric>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <utility>
  19. #include <vector>
  20.  
  21. using namespace std;
  22.  
  23. #define MP make_pair
  24. #define all(v) (v).begin(), (v).end()
  25.  
  26. typedef vector<int> vi;
  27. typedef vector<vi> vvi;
  28. typedef vector<vvi> vvvi;
  29. typedef vector<bool> vb;
  30. typedef vector<vb> vvb;
  31. typedef vector<vvb> vvvb;
  32. typedef long double ld;
  33. typedef pair<int, int> pii;
  34. typedef long long ll;
  35. typedef vector<ll> vl;
  36. typedef vector<vl> vvl;
  37. typedef vector<vvl> vvvl;
  38. typedef pair<ll, ll> pll;
  39. typedef vector<double> vd;
  40. typedef vector<vd> vvd;
  41. typedef vector<vvd> vvvd;
  42.  
  43. ll CountLeq(ll x, int power) {
  44.   if (power == 1) {
  45.     return x - 1;
  46.   }
  47.   double t = pow(double(x), 1.0 / power);
  48.   for (int ans = ceil(t) + 2; ; --ans) {
  49.     ll powans = 1;
  50.     bool good = true;
  51.     for (int i = 1; i <= power; ++i) {
  52.       if (x / ans >= powans) {
  53.         powans *= ans;
  54.       } else {
  55.         good = false;
  56.         break;
  57.       }
  58.     }
  59.     if (good && powans <= x) {
  60.       return ans - 1;
  61.     }
  62.   }
  63. }
  64.  
  65. ll CountLeq(ll x, const vi& coeffs) {
  66.   if (x == 1) {
  67.     return 1;
  68.   }
  69.   ll result = 1;
  70.   for (int i = 1; i < coeffs.size(); ++i) {
  71.     if (coeffs[i]) {
  72.       result += CountLeq(x, i) * coeffs[i];
  73.     }
  74.   }
  75.   return result;
  76. }
  77.  
  78. int main() {
  79.   int tests;
  80.   cin >> tests;
  81.   for (int test_index = 0; test_index < tests; ++test_index) {
  82.     int N, m;
  83.     scanf("%d%d", &N, &m);
  84.     vi pows(m);
  85.     for (int i = 0; i < m; ++i) {
  86.       scanf("%d", &pows[i]);
  87.     }
  88.     sort(pows.begin(), pows.end());
  89.     vb is_needed(61, false);
  90.     for (int i = 0; i < pows.size(); ++i) {
  91.       for (int j = 1; j * pows[i] < 61; ++j) {
  92.         is_needed[j * pows[i]] = true;
  93.       }
  94.     }
  95.     vi coeffs(61, 0);
  96.     for (int i = 1; i < 61; ++i) {
  97.       if (!is_needed[i]) {
  98.         continue;
  99.       }
  100.       int sum = 0;
  101.       for (int j = 1; j < i; ++j) {
  102.         if (i % j == 0) {
  103.           sum += coeffs[j];
  104.         }
  105.       }
  106.       coeffs[i] = 1 - sum;
  107.     }
  108.     ll low = 1;
  109.     ll high = ll(1000000000) * ll(100000000);
  110.     while (low < high) {
  111.       ll mid = (low + high) / 2;
  112.       ll less_x = CountLeq(mid, coeffs);
  113.       if (less_x < N) {
  114.         low = mid + 1;
  115.       } else {
  116.         high = mid;
  117.       }
  118.     }   
  119.     cout << low << endl;
  120.   }
  121.   return 0;
  122. }
  123.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wjDrks
language:
C++14 (gcc 8.3)
created:
8 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!