#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; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter