fork(1) download
copy 
  1. #include <iostream>
  2. #include<vector>
  3.  
  4. using namespace std;
  5.  
  6.  
  7.  
  8. int main()
  9. {
  10.     int t;
  11.     cin>>t;
  12.     while(t--)
  13.     {
  14.         int n;
  15.         cin>>n;
  16.         vector<int>arr(n+1);
  17.         arr[0]=0;
  18.         for(int i=1;i<=n;i++)
  19.         cin>>arr[i];
  20.         vector<int>startindex(n+1,0);
  21.         vector<int>primearr(1001,0);
  22.  
  23.         for(int i=1;i<=n;i++)
  24.         {
  25.             int seen=0;
  26.             int pr=arr[i];
  27.             vector<int>primes;
  28.             if(pr%2==0)
  29.             {
  30.                 while(pr%2==0)
  31.                 {
  32.                     primes.push_back(2);
  33.                     pr=pr/2;
  34.                 }
  35.             }
  36.             for(int j=3;j*j<=pr;j+=2)
  37.             {
  38.                 while(pr%j==0)
  39.                 {
  40.                     primes.push_back(j);
  41.                     pr=pr/j;
  42.                 }
  43.             }
  44.             if(pr>1)
  45.             primes.push_back(pr);
  46.             for(int j=0;j<primes.size();j++)
  47.             {
  48.                 int pr1=primes[j];
  49.                 if(primearr[pr1]>seen)
  50.                 seen=primearr[pr1];
  51.                 primearr[pr1]=i;
  52.             }
  53.             startindex[i]=(seen>startindex[i-1]?seen:startindex[i-1]);
  54.             primes.clear();
  55.         }
  56.         long long count=0;
  57.         for(int i=1;i<=n;i++)
  58.         {
  59.             count=count+(i-startindex[i]);
  60.         }
  61.         cout<<count<<endl;
  62.     }
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
5
2
1 1
4
2 1 1 2
8
11 3 1 3 7 7 11 1
1
144
11
2 1 5 8 12 6 100 14 49 42 65
stdout
copy 
3
9
17
0
11
https://ideone.com/xMR08s
language:
C++14 (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!