fork download 
  1. #include <iostream>
  2. #include <math.h>
  3. #include <algorithm>
  4. #include <map>
  5. #include <vector>
  6. #include <queue>
  7. #include <iomanip>
  8. #include <set>
  9. #include <list>
  10. #include <string>
  11. #include <memory.h>
  12. #include <bitset>
  13. #include <stack>
  14. using namespace std;
  15. #define ll long long
  16. #define ppi pair<int , int>
  17. #define mp make_pair
  18. using namespace std; 
  19.  
  20. const int MAXN  =  2*1e7; 
  21.  
  22. // stores smallest prime factor for every number 
  23. int spf[MAXN]; 
  24.  
  25. // Calculating SPF (Smallest Prime Factor) for every 
  26. // number till MAXN. 
  27. // Time Complexity : O(nloglogn) 
  28. void sieve() 
  29. { 
  30.     spf[1] = 1; 
  31.     for (int i=2; i<MAXN; i++) 
  32.  
  33.         // marking smallest prime factor for every 
  34.         // number to be itself. 
  35.         spf[i] = i; 
  36.  
  37.     // separately marking spf for every even 
  38.     // number as 2 
  39.     for (int i=4; i<MAXN; i+=2) 
  40.         spf[i] = 2; 
  41.  
  42.     for (int i=3; i*i<MAXN; i++) 
  43.     { 
  44.         // checking if i is prime 
  45.         if (spf[i] == i) 
  46.         { 
  47.             // marking SPF for all numbers divisible by i 
  48.             for (int j=i*i; j<MAXN; j+=i) 
  49.  
  50.                 // marking spf[j] if it is not  
  51.                 // previously marked 
  52.                 if (spf[j]==j) 
  53.                     spf[j] = i; 
  54.         } 
  55.     } 
  56. } 
  57.  
  58. // A O(log n) function returning primefactorization 
  59. // by dividing by smallest prime factor at every step 
  60. vector<ppi> getFactorization(int x) 
  61. { 
  62.     map<int , int> ret; 
  63.     while (x != 1) 
  64.     { 
  65.         ret[spf[x]]++;
  66.         x = x / spf[x]; 
  67.     } 
  68.     vector<ppi> ans;
  69.     for (auto it = ret.begin();it != ret.end();it++)
  70.         ans.push_back(mp(it->first , it->second));
  71.     return ans; 
  72. } 
  73.   int gcd(int a, int b) 
  74. { 
  75.     if (a == 0) 
  76.         return b; 
  77.     return gcd(b % a, a); 
  78. } 
  79.  
  80. // Function to find gcd of array of 
  81. // numbers 
  82. int findGCD(vector<int> &arr) 
  83. { 
  84.     int n = arr.size();
  85.     int result = arr[0]; 
  86.     for (int i = 1; i < n; i++) 
  87.         result = gcd(arr[i], result); 
  88.  
  89.     return result; 
  90. } 
  91. map<int , int> vq;
  92. map<int , ppi> mnvq;
  93. int main()
  94. {
  95. #ifndef ONLINE_JUDGE
  96.     freopen("/Users/rababagames/Desktop/cpp/inp.txt", "r", stdin);
  97.     freopen("/Users/rababagames/Desktop/cpp/out.txt", "w", stdout);
  98. #endif
  99. sieve();
  100.     int n;
  101.     cin >> n;
  102.     int one = 0 , other = 0;
  103.     vector<int> gdans;
  104.     for (int i =0 ; i < n ; i ++)
  105.     {
  106.         int val;
  107.         scanf("%d"  , &val);
  108.         if (val == 1) one++;
  109.          else
  110.         {
  111.             other = 1;
  112.             vector<ppi> ans= getFactorization(val);
  113.                 gdans.push_back(val);
  114.             for (int j = 0 ; j < ans.size() ;j++)
  115.             {
  116.                 vq[ans[j].first]++;
  117.                 ppi sn = mnvq[ans[j].first];
  118.                 if (ans[j].second == sn.first)
  119.                     mnvq[ans[j].first].second++;
  120.                 else if (ans[j].second < sn.first || !sn.first)
  121.                     mnvq[ans[j].first] = mp(ans[j].second , 1);
  122.             }
  123.         }
  124.     }
  125.     int mn = 1e9;
  126.     n-=one;
  127.     for (auto it = vq.begin() ; it != vq.end() ; it++)
  128.     {
  129.         int u = it->second;
  130.         if (u != n)
  131.         {
  132.             mn = min(mn , n - u);
  133.         }
  134.         else 
  135.         {
  136.             mn = min(mn , mnvq[it->first].second);
  137.         }
  138.     }
  139.     int gd = 1;
  140.     if (gdans.size())
  141.     gd = findGCD(gdans);
  142.     if (one && gd > 1)
  143.     {
  144.         cout << one;
  145.     }
  146.     else if (mn == 1e9)
  147.     {
  148.         cout << -1;
  149.     }
  150.     else if (n == mn)
  151.     {
  152.         cout << -1;
  153.     }
  154.     else cout << mn + one;
  155.     return 0;
  156. }
Success #stdin #stdout 0.24s 93376KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/zHLllz
language:
C++ (gcc 8.3)
created:
6 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!