fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <string.h>
  5. using namespace std;
  6.  
  7. int t;
  8. int n;
  9. int nums[100001];
  10. vector<int> Primes[1000001];
  11.  
  12. int Counter[1000001];
  13. int MoreThanOneCounter=0;
  14.  
  15. bool IsPrime[1000001];
  16.  
  17. void Add(int x)
  18. {
  19.     int i;
  20.  
  21.     for (i=0;i<Primes[x].size();i++)
  22.     {
  23.         Counter[ Primes[x][i] ]++;
  24.         if (Counter[ Primes[x][i] ]>1)
  25.         {
  26.             MoreThanOneCounter++;
  27.         }
  28.     }
  29.  
  30.     return;
  31. }
  32.  
  33. void Remove(int x)
  34. {
  35.     int i;
  36.  
  37.     for (i=0;i<Primes[x].size();i++)
  38.     {
  39.         Counter[ Primes[x][i] ]--;
  40.         if (Counter[ Primes[x][i] ]==1)
  41.         {
  42.             MoreThanOneCounter--;
  43.         }
  44.     }
  45.  
  46.     return;
  47. }
  48.  
  49. int main()
  50. {
  51.     //freopen("sample.txt","r",stdin);
  52.  
  53.     int test;
  54.     int i,j;
  55.     int cp;
  56.     int l,r;
  57.     int ans=-1;
  58.  
  59.     for (i=1;i<=1000000;i++)
  60.     {
  61.         IsPrime[i]=true;
  62.     }
  63.     IsPrime[1]=false;
  64.  
  65.     for (i=2;i<=1000000;i++)
  66.     {
  67.         if (IsPrime[i])
  68.         {
  69.             Primes[i].push_back(i);
  70.  
  71.             for (j=i+i;j<=1000000;j+=i)
  72.             {
  73.                 Primes[j].push_back(i);
  74.                 IsPrime[j]=false;
  75.             }
  76.         }
  77.     }
  78.  
  79.     scanf("%d",&t);
  80.  
  81.     for (test=1;test<=t;test++)
  82.     {
  83.         memset(Counter,0,sizeof(Counter));
  84.  
  85.         scanf("%d",&n);
  86.  
  87.         for (i=1;i<=n;i++)
  88.         {
  89.             scanf("%d",&nums[i]);
  90.         }
  91.  
  92.         l=1;
  93.         r=1;
  94.         Add(nums[1]);
  95.  
  96.         ans=-1;
  97.         while(l<=n)
  98.         {
  99.             while(MoreThanOneCounter>0)
  100.             {
  101.                 Remove(nums[l]);
  102.                 l++;
  103.             }
  104.  
  105.             if (r-l+1>ans && r-l+1>1)
  106.             ans=r-l+1;
  107.  
  108.             if (r==n)
  109.             break;
  110.  
  111.             r++;
  112.             Add(nums[r]);
  113.         }
  114.  
  115.         printf("%d\n",ans);
  116.     }
  117.  
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0.73s 43568KB
comments (?)
stdin
copy 
3
2
7 2
4
2 2 3 4
3
2 2 4
stdout
copy 
2
2
-1
https://ideone.com/e22PJB
language:
C++ (gcc 8.3)
created:
10 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!