一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

0近似gcd - 蓝桥云课 (lanqiao.cn)

---

二、解题报告

1、思路分析

考虑近似gcd的子数组的特点：不为g的倍数的数字个数小于等于1

我们用前缀和pre[]来存储不为g的倍数的数字个数

那么枚举左端点l，找到最靠右的r，满足pre[r] - pre[l - 1] <= 1

那么左端点l的贡献就是r - l - 1

l  递增，那么r也递增

我们可以选择二分或者双指针

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

from bisect import *

n, g = map(int, input().split())

l = r = 0
a = list(map(int, input().split()))

pre = [0] * (n + 1)
for i in range(1, n + 1):
    pre[i] = pre[i - 1] + (1 if a[i - 1] % g else 0)
r = 2
res = 0
for l in range(1, n):
    while r <= n and pre[r] - pre[l - 1] <= 1:
        r += 1
    res += r - l - 1

print(res   )