sliding window gcd(try 1)

PHOTO EMBED

Thu Nov 26 2020 14:13:55 GMT+0000 (UTC)

Saved by @Shami_Al #c++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
ll cs=0;
ll tab[500000][20];
void spar(ll a[],ll n)
{
    ll i,j;
    for(i=0;i<n;i++)
        tab[i][0]=a[i];
    for(j=1;(1<<j)<=n;j++)
    {
        for(i=0;i+(1<<(j-1))-1<n;i++)
            tab[i][j]=__gcd(tab[i][j-1],tab[i+(1<<(j-1))][j-1]);
    }
}
ll qry(ll a,ll b)
{
    ll j=log2(b-a+1);
    return __gcd(tab[a][j],tab[b-(1<<j)+1][j]);
}
void sol()
{
    ll n,m,i,sum=0;
    cin>>n>>m;
    ll a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    spar(a,n);
    for(i=0;i+m-1<n;i++)
        sum+=qry(i,i+m-1);
    cout<<sum;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //ll t;
    //cin>>t;
    //while(t--)
    sol();
    return 0;
}
content_copyCOPY