fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e3+3;
  4. const int M=1e6;
  5. const long long inf=1e18+3;
  6. #define ll long long
  7. #define fi first
  8. #define se second
  9. #define pi pair
  10. int e[M+3];
  11. int b[M+3];
  12. int snt[M+3];
  13. int k=0;
  14. void sang()
  15. {
  16.     for(int i=1;i<=M;i++)
  17.     {
  18.         e[i]=i;
  19.     }
  20.     for(int i=2;i*i<=M;i++)
  21.     {
  22.         if(e[i]==i)
  23.         {
  24.             for(int j=i+i;j<=M;j+=i)
  25.             {
  26.                 e[j]=i;
  27.             }
  28.         }
  29.     }
  30.     for(int i=2;i<=M;i++)
  31.     {
  32.         if(e[i]==i)
  33.         {
  34.             snt[++k]=i;
  35.         }
  36.     }
  37. }
  38. long long a[N];
  39. int main(){
  40.  
  41.     cin.tie(0)->sync_with_stdio(0);
  42.     int n;
  43.     cin>>n;
  44.     long long mu=0;
  45.     for(int i=1;i<=n;i++)
  46.     {
  47.         cin>>a[i];
  48.         mu=max(mu,a[i]);
  49.     }
  50.     if(mu<=M)
  51.     {
  52.         sang();
  53.         for(int u=1;u<=k;u++)
  54.         {
  55.             for(int i=1;i<=n;i++)
  56.             {
  57.                 if(a[i]%snt[u]==0)
  58.                 {
  59.                     b[u]++;
  60.                 }
  61.             }
  62.         }
  63.         int ma=0;
  64.         for(int i=1;i<=k;i++)
  65.         {
  66.             ma=max(ma,b[i]);
  67.         }
  68.         cout<<ma;
  69.         return 0;
  70.     }
  71.     int ma=1;
  72.     for(int i=1;i<=n;i++)
  73.     {
  74.         long long  gcd=0;
  75.         int tmp=1;
  76.         for(int j=1;j<=n;j++)
  77.         {
  78.             if(i!=j && __gcd(gcd,a[j])!=1)
  79.             {
  80.                 tmp++;
  81.                 gcd=__gcd(gcd,a[j]);
  82.             }
  83.         }
  84.         ma=max(ma,tmp);
  85.     }
  86.     cout<<ma;
  87. }
  88.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
10
30 30 2 2 15 15 15 15 15 2000000000
stdout
copy 
6
https://ideone.com/g6579f
problem DQUERY, based on SPOJ submission 17665944 (C++14), 2016-09-07 14:18:17
language:
C++14 (gcc 8.3)
created:
3 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!