fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. ll a[500005];
  5. ll dp[500005][50];
  6. int main()
  7. {
  8.     ll i,j,k,n,m,t,s,l;
  9.     scanf("%I64d",&n);
  10.     for(i=0;i<n;i++)
  11.     {
  12.         scanf("%I64d",&a[i]);
  13.         dp[i][0]=a[i];
  14.     }
  15.     ll dep=log2(n)+1;
  16.     for(i=0;i<n;i++)
  17.     {
  18.       for(j=1;j<=dep;j++)
  19.       {
  20.           if(i+(1<<j)-1<n)
  21.           {
  22.               dp[i][j]=__gcd(dp[i][j-1],dp[i+(1<<j)-1][j-1]);
  23.           }
  24.       }
  25.     }
  26.     set<ll>st;
  27.     for(i=0;i<n;i++)
  28.     {
  29.        ll cur=a[i];
  30.        if(cur==1)
  31.        {
  32.            st.insert(1);
  33.            continue;
  34.        }
  35.        ll s=i;
  36.        while(1)
  37.        {
  38.            ll lo=s,hi=n-1,ans=-1,gc=-1;
  39.            while(lo<=hi)
  40.            {
  41.                ll mi=(lo+hi)/2;
  42.                ll len=log2(mi-i+1);
  43.                ll cal=__gcd(dp[s][len],dp[mi-(1<<len)+1][len]);
  44.                if(cal<cur)
  45.                {
  46.                    gc=cal;
  47.                    hi=mi-1;
  48.                }
  49.                else ans=mi,lo=mi+1;
  50.            }
  51.            st.insert(cur);
  52.            s=ans+1;
  53.            if(s==n) break;
  54.             cur=gc;
  55.             if(cur==1)
  56.             {
  57.                 st.insert(cur);
  58.                 break;
  59.             }
  60.        }
  61.     }
  62.     printf("%d",st.size());
  63.  
  64. }
  65.  
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/zeDVkD
language:
C++14 (clang 8.0)
created:
5 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!