fork download
copy 
  1. // d
  2. // Author: _Sherbiny
  3.  
  4. #include "bits/stdc++.h"
  5. using namespace std;
  6. using ll = long long;
  7. #define endl '\n'
  8. #define int ll
  9. //====================//
  10.  
  11. vector<int> prime_factorization(ll num) {
  12.  
  13.     vector<int> factors;
  14.  
  15.     if (num < 2) return factors;
  16.  
  17.     while (!(num % 2)) {
  18.         factors.push_back(2);
  19.         num /= 2;
  20.     }
  21.  
  22.     for (ll i = 3; i * i <= num; i += 2) {
  23.         while (!(num % i)) {
  24.             factors.push_back(i);
  25.             num /= i;
  26.         }
  27.     }
  28.  
  29.     if (num > 1) factors.push_back(num);
  30.  
  31.     return factors;
  32. }
  33. void magic() {
  34.     int n; cin >> n;
  35.     vector<int> v(n);
  36.     map<int, int> mp;
  37.  
  38.     set<int> s;
  39.     for(int &i: v) {
  40.         cin >> i;
  41.         s.insert(i);
  42.     }
  43.  
  44.     auto calc=[&](int x) {
  45.         vector<int> pr = prime_factorization(x);
  46.         for(auto &xx : pr) mp[xx] = 1;
  47.     };
  48.  
  49.     if(*s.begin() == 1) s.erase(s.begin());
  50.     if(s.size() > 0) calc(*s.begin());
  51.     if(s.size() > 1) calc(*next(s.begin()));
  52.     if(s.size() > 1) calc(*next(s.begin()) - *s.begin());
  53.  
  54.  
  55.     int ans = n;
  56.     for(auto &[a, b]: mp) {
  57.         int md = 0, good = 1;
  58.         int c = 0;
  59.         for(int &i: v) {
  60.             if(!(i % a)) continue;
  61.             if(md && md != i % a) good = 0;
  62.             md = i % a;
  63.             c++;
  64.         }
  65.  
  66.         if(good) ans = min(ans, c);
  67.     }
  68.  
  69.     cout << ans << endl;
  70. }
  71.  
  72. signed main() {
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0), cout.tie(0);
  75.  
  76.     int t = 1;
  77.     while (t--) magic();
  78. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/TN2rWV
language:
C++ (gcc 8.3)
created:
2 days 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!