目录

1.近似GCD1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接 2.解题思路3.Ac_code1.C++2.Python

1.近似GCD

1.题目描述

小蓝有一个长度为 n n n 的数组 A = ( a 1 , a 2 , ⋯   , a n ) A=\left(a_{1}, a_{2}, \cdots, a_{n}\right) A=(a1​,a2​,⋯,an​), 数组的子数组被定义为从 原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数 组中所有元素的最大公约数。如果最多更改数组中的一个元素之后, 数组的最 大公约数为 g g g, 那么称 g g g 为这个数组的近似 GCD。一个数组的近似 GCD 可能 有多种取值。

具体的, 判断 g g g 是否为一个子数组的近似 GCD 如下:

如果这个子数组的最大公约数就是 g g g, 那么说明 g g g 是其近似 GCD。

在修改这个子数组中的一个元素之后 (可以改成想要的任何值), 子数 组的最大公约数为 g g g, 那么说明 g g g 是这个子数组的近似 GCD。

小蓝想知道, 数组 A ​ A​ A​ 有多少个长度大于等于 2 的子数组满足近似 GCD 的值为 g ​ g​ g​.

2.输入格式

输入的第一行包含两个整数 n , g n,g n,g，用一个空格分隔，分别表示数组 A A A 的长度和 g g g 的值。
第二行包含 n n n 个正数 a 1 , a 2 , ⋯ , a n , a_1,a_2,⋯,a_n, a1​,a2​,⋯,an​, 相邻两个整数之间用一个空格分隔。

3.输出格式

输出一行包含一个整数表示数组 A A A 有多少个长度大于等于 2 的子数组的近 似 GCD 的值为 g g g 。

4.样例输入

5 3
1 3 6 4 10

5.样例输出

5

6.数据范围

2 ≤ n ≤ 1 0 5 , 1 ≤ g , a i ≤ 1 0 9 。 2≤n≤10^5,1≤g,ai≤10^9。 2≤n≤105,1≤g,ai≤109。

7.原题链接

近似GCD

2.解题思路

首先，如果一个数是g的倍数，那我们称其为符合条件的数。如果一个数组的近似GCD为 g g g，那么该数组最多只能有一个数不符合条件。为什么呢？因为如果只有一个不符合条件的数话，我们将其变为g，那么该数组的GCD将为g。如果数组全部符合条件呢？那我们只需要随便将其中一个数变为g，该数组的GCD也将为g。

那么现在问题就转换为存在多少个长度大于2的子数组使得子数组内最多只存在一个不符合条件的数，这个问题我们可以使用双指针解决。右指针r遍历数组的每一个数，左指针l将是以r将作为子数组的右端点的情况下，左端点能最远能到达的距离，也就是使得 [ l , r ] [l,r] [l,r]区间最多只存在一个不符合条件的数，且 l l l 和 r r r 之间的距离尽可能长。这样的话，数组 [ l , r ] [l,r] [l,r], [ l + 1 , r ] [l+1,r] [l+1,r], [ l + 2 , r ] [l+2,r] [l+2,r]… [ r − 1 , r ] [r-1,r] [r−1,r]都是符合条件的答案，总共是r-l个。对于数组的每一个数我们都将其作为r后，累加答案即可。

我们考虑变换数组的值，如果其是符合条件的数，我们将其值赋为1，否则赋为0，对于区间 [ l , r ] [l,r] [l,r]是否为符合条件的子数组，只需要判断 s u m [ l , r ] sum[l,r] sum[l,r]是否大于等于 r − l r-l r−l。求区间和 s u m sum sum，我们可以使用前缀和数组直接获取，但由于是双指针，也可以同时维护，这里代码使用了前缀和数组。

时间复杂度: O ( n ) O(n) O(n)。

3.Ac_code

1.C++

#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n, g;void solve(){cin >> n >> g;std::vector<int> a(n + 1);for (int i = 1; i <= n; ++i) {int x;cin >> x;a[i] = (x % g == 0);a[i] += a[i - 1];}int l = 0;LL ans = 0;for (int r = 2; r <= n; ++r) {while (l + 1 < r && a[r] - a[l] < r - l - 1) l++;ans += r - l -1;}cout << ans << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}

2.Python

n,g=map(int,input().split())a=list(map(int,input().split()))a=[0]+aans=0#记录上一个不符合条件的数last=0#记录符合条件子数组的左区间l=1for r in range(1,n+1):    if a[r]%g!=0:        l=last+1        last=r    ans=ans+(r-l)print(ans)