fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define int long long
  6.  
  7. const int N = 300002;
  8. const int INF = 1e9;
  9. const int mod = 1e9+7;
  10.  
  11. int mob[N];
  12. int lpf[N];
  13. int fre[N];
  14. int cnt[N];
  15.  
  16. void sieve(){
  17.     for(int i=2;i<N;++i){
  18.         if(!lpf[i])
  19.         for(int j=i;j<N;j+=i)if(!lpf[j])lpf[j]=i;
  20.     }
  21. }
  22.  
  23. void mobius(){
  24.     mob[1]=1;
  25.     for(int i=2;i<N;++i){
  26.         if (lpf[i/lpf[i]]==lpf[i])mob[i]=0;
  27.         else mob[i]=-1 * (mob[i/lpf[i]]);
  28.     }
  29. }
  30.  
  31.  
  32. __int128 C(int a, int b){
  33.     __int128 res=1;
  34.     for(int i=a-b+1;i<=a;++i){
  35.         res *= i;
  36.     }
  37.     for(int i=1;i<=b;++i)res/=i;
  38.     return res;
  39. }
  40.  
  41.  
  42. signed main() {
  43.     ios::sync_with_stdio(false);
  44.     cin.tie(nullptr);
  45.     // freopen("bhlt_bai5.inp","r",stdin);
  46.     // freopen("bhlt_bai5.out","w",stdout);
  47.     sieve();
  48.     mobius();
  49.     int n; cin  >> n;
  50.     vector<int> ar(n);
  51.     int maxA=0;
  52.     for(int i=0;i<n;++i)cin>>ar[i],fre[ar[i]]++,maxA=max(maxA,ar[i]);
  53.     int g=ar[0];
  54.     for(int i=1;i<n;++i)g=__gcd(g,ar[i]);
  55.     if (g != 1){
  56.         return (cout << -1),0;
  57.     }
  58.     for(int i=1;i<=maxA;++i){
  59.         for(int j=i;j<=maxA;j+=i)cnt[i]+=fre[j];
  60.     }
  61.     for (int k = 1; k <= n; ++k) {
  62.         __int128 sum = 0;
  63.         for (int d = 1; d <= maxA; ++d) {
  64.             if (cnt[d] < k) continue;
  65.             sum += (__int128)mob[d] * C(cnt[d], k);
  66.         }
  67.         if (sum > 0) {
  68.             cout << k << "\n";
  69.             return 0;
  70.         }
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.02s 8132KB
comments (?)
stdin 
3
66 70 21
stdout 
3
https://ideone.com/cjDaoJ
language:
C++14 (clang 8.0)
created:
11 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!