第十三届蓝桥杯国赛 C++ C组 F 题、Python B组 E 题——近似GCD(AC)
1.近似GCD
1.题目描述
小蓝有一个长度为 n n n 的数组 A = ( a 1 , a 2 , ⋯ , a n ) A=left(a_{1}, a_{2}, cdots, a_{n} ight) 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.原题链接
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
后,累加答案即可。
但是对于每个数的上界l
我们该如何考虑呢?如果是符合条件的数,那么它的上界是上两个不符合条件的数的下一个数。就比如下标c
是符合条件的数,在它之前上一个不符合条件的数下标是b
,再往前一个不符合条件的数的下标为a
,那么c
的上界下标l
应该指向a+1
。如果是不符合条件的数,那么很明显它的上界应该是上一个不符合条件的数的下一个数。 同样假设下标c
的上一个不符合条件的数的下标为b
,那么它的上界就应该是b+1
。明白了这个过程后,我们使用变量last
来记录上一次不符合条件的数的位置,每次遇到不符合条件的数,就将l
和last
更新。
当然上述双指针做法过于抽象,我们考虑变换数组的值,如果其是符合条件的数,我们将其值赋为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++
代码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
",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 << '
';
}
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)
相关文章
- 堡垒机怎么登录服务器?堡垒机有什么作用?
- 最新Eclipse安装教程(2022-09)
- 堡垒机怎么登录生产服务器?堡垒机有什么功能?
- linux 网络带宽和延时测试
- 七种常用的设计模式
- 堡垒机怎么看服务器分配的账号?具体步骤是怎样的?
- 分布式架构-可观测性-事件日志
- 【《操作系统慕课版》合集】期末复习 + 核心算法整理 + 课后答案
- 正则表达式基础
- 【Spring6】| Bean的四种获取方式(实例化)
- 堡垒机怎么添加linux服务器?具体步骤是什么?
- 聊聊性能优化模式
- DRF三级视图
- 网易二面:CPU狂飙900%,该怎么处理?
- 本地堡垒机服务器传文件的方法 堡垒机都有什么作用
- DRF分页
- DRF视图集
- 多业务下api网关如何部署 如何对服务进行拆分?
- 20多年老码农的IT学习之路
- 服务器堡垒机错误码110的原因?错误码110如何解决?