蓝桥杯练习题 近似GCD 双指针

题目

小蓝有一个长度为 n 的数组 4 =(a1, a2,··,an),数组的了数组被定义为从 原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数 组中所有元素的最大公约数。
如果最多更改数组中的一个元素之后,数组的最大公约数为 g,那么称 g 为这个数组的近似GCD。
一个数组的近似 GCD 可能有多种取值。
具体的,判断 g 是否为一个数组的近似 GCD 如下
1.如果这个子数组的最大公约数就是 g,那么说明 g 是其近似GCD.
2.在修改这个子数组中的一个元素之后(可以改成想要的任何值),数组的最大公约数为 g,那么说明 g 是这个了数组的近似 GCD。
小蓝想知道数组 A有多少个长度大于等于 2的子数组满足近似GCD的值为 g。

输入格式

输入的第一行包含两个整数 n,g,用一个空格分隔,分别表示数组 A的长度和 g 的值 第二行包含 n 个整数 a1,a2,··,an,相两个整数之间用一个空格分隔

代码

import math
n,g=map(int,input().split())
a=[0]+list(map(int,input().split()))
 
re=0
left=1
right=1
temp=0#记录的上一个不是g的数的位置
for right in range(1,n+1):
    t=math.gcd(g,a[right])
    if t != g:#如果当前这个数不是g的倍数
        left=temp+1
        temp=right
    if right-left+1>=2:re+=right-left
print(re)
 

代码分析