第十三届蓝桥杯国赛真题 近似gcd

双指针, 用一个指针 i 表示， 表示 以 i 结尾的子数组修改一次后左端最远 延伸到 j , 那么以 i 结尾的子数组 左端取任意的 j ~ i - 1 都是满足条件的子数组

满分代码

#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1e5 + 10;
 
int n, g;
int a[N];
 
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
 
int main()
{
    scanf("%d%d", &n, &g);
 
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
 
    int last = 0;
    long long res = 0;
    for (int i = 1, j = 1; i <= n; i ++ )
    {
        int t = gcd(g, a[i]);
        if (t != g) j = last + 1, last = i;
        if (i - j + 1 >= 2) res += i - j;
    }
 
    printf("%lld", res);
 
    return 0;
}