C++双指针优化

解题思路:纯暴力大概只能拿个40 发现可以采用双指针优化 利用一个p来维护左边界 枚举序列当它满足近似gcd那么所以子序列都满足 ans加上即可

注意事项:

参考代码:

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N =1e5+10;

int n,k,p,ans;//p用来维护下标

int arr[N];

signed main()

{   

    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);

    cin>>n>>k;

    for(int i=1;i<=n;i++) cin>>arr[i];

    //用双指针枚举端点如果 当前序列满足近似gcd那么子序列全部都满足

    ans=-n;//提前去除长度为1的数组

    for(int l=0,r=1;r<=n;r++){

        if(__gcd(k,arr[r])!=k){

            l=p,p=r;

        }

        ans+=(r-l);

    }

    cout<<ans<<endl;

    return 0;

}