pastebin

pastebin

Paste Search Dynamic
Recent pastes
getDivisors
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define read(type) readInt<type>() // Fast read
  4. #define ll long long
  5. #define nL "n"
  6. #define pb push_back
  7. #define mk make_pair
  8. #define pii pair<int, int>
  9. #define a first
  10. #define b second
  11. #define vi vector<int>
  12. #define all(x) (x).begin(), (x).end()
  13. #define umap unordered_map
  14. #define uset unordered_set
  15. #define MOD 1000000007
  16. #define imax INT_MAX
  17. #define imin INT_MIN
  18. #define exp 1e9
  19. #define sz(x) (int((x).size()))
  20.  
  21. vector<int> getDivisors(int n)
  22. {  
  23.     vector<int> res;
  24.     for (int i=1; i<=sqrt(n); i++)
  25.     {
  26.         if (n%i == 0)
  27.         {
  28.             // If divisors are equal, print only one
  29.             if (n/i == i)
  30.                 res.pb(i);
  31.  
  32.             else // Otherwise print both
  33.                 res.pb(i);
  34.                 res.pb(n/i);
  35.         }
  36.     }
  37.     return res;
  38. }
  39.  
  40. void solve() {
  41.     int n, m; cin >> n >> m;
  42.     set<int> topics;
  43.     for(auto i = 2; i <= m; i++) {topics.insert(i);}
  44.  
  45.     set<int> stu; for(auto i = 0; i < n; i++) {int d; cin >> d; stu.insert(d);}
  46.  
  47.     int miv = int_max;
  48.     int mav = int_min;
  49.  
  50.     vector<int> mivAble;
  51.  
  52.     for(auto itr = stu.begin(); itr != stu.end(); itr++) {
  53.         int prevS = topics.size();
  54.         for(auto val : getDivisors(*itr)) {
  55.             topics.erase(val);
  56.  
  57.             if (topics.find(val) != topics.end()) {mivAble.pb(val);}  
  58.         }
  59.         if (prevS > (int)topics.size()) {
  60.             if (miv > *itr) {miv = *itr;}
  61.             else {mivAble = {};}
  62.             if (mav < *itr) {mav = *itr;}
  63.            
  64.         }
  65.     }
  66.  
  67.     if ((int)topics.size() == 0) {
  68.         auto loopItr = stu.upper_bound(miv);
  69.         while (*loopItr < mav) {
  70.             bool vaild = true;
  71.             for(auto div : mivAble) {
  72.                 if (*loopItr % div != 0) {vaild = false;}
  73.             }
  74.             if (vaild) {
  75.                 miv = *loopItr;
  76.             }
  77.  
  78.             loopItr++;
  79.         }
  80.  
  81.         cout << mav - miv << endl;
  82.     } else {
  83.         cout << -1 << endl;
  84.     }
  85. }
  86.  
  87.  
  88.  
  89. int32_t main()
  90. {
  91.     ios_base::sync_with_stdio(false);
  92.     cin.tie(null);
  93.     int t; cin >> t;
  94.     while (t--) {
  95.         solve();
  96.     }
  97.    
  98.     return 0;
  99. }
Parsed in 0.028 seconds