第十三届蓝桥杯国赛 C++ C组 F 题、Python B组 E 题——近似GCD（AC）

1.近似GCD

1.题目描述

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

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

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

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

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

2.输入格式

输入的第一行包含两个整数 $n,g$用一个空格分隔分别表示数组 $A$ 的长度和 $g$ 的值。
第二行包含 $n$ 个正数 $a_1,a_2,\cdots ,a_n,$ 相邻两个整数之间用一个空格分隔。

3.输出格式

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

4.样例输入

5 3
1 3 6 4 10

5.样例输出

5

6.数据范围

$2\le n\le 10^5,1\le g,ai\le 10^9。$

7.原题链接

近似GCD

2.解题思路

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

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

但是对于每个数的上界l我们该如何考虑呢如果是符合条件的数那么它的上界是上两个不符合条件的数的下一个数。就比如下标c是符合条件的数在它之前上一个不符合条件的数下标是b再往前一个不符合条件的数的下标为a那么c的上界下标l应该指向a+1。如果是不符合条件的数那么很明显它的上界应该是上一个不符合条件的数的下一个数。 同样假设下标c的上一个不符合条件的数的下标为b那么它的上界就应该是b+1。明白了这个过程后我们使用变量last来记录上一次不符合条件的数的位置每次遇到不符合条件的数就将l和last更新。

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

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

3.Ac_code

1.C++

代码1:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;

int n,g;
int a[N];

int main() 
{
	scanf("%d%d",&n,&g);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	LL ans=0;
	//记录上一个不符合条件的数
	int last=0;
	//记录符合条件子数组的左区间
	int l=1;
	for(int r=1;r<=n;++r){
        //判断它是否是符合条件的数
		bool t=a[r]%g==0;
		if(!t){
		   //时刻保证区间内不符合条件的数只能有一个
		   l=last+1,last=r;
		}
		//累加答案
		ans+=r-l;
	}
	printf("%lld\n",ans);
    return 0;
}

代码2

#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]+a
ans=0#记录上一个不符合条件的数
last=0#记录符合条件子数组的左区间
l=1
for r in range(1,n+1):
    if a[r]%g!=0:
        l=last+1
        last=r
    ans=ans+(r-l)
print(ans)