P8809 [蓝桥杯 2022 国 C] 近似 GCD 题解

解法一
枚举区间左端点和右端点，扫描区间，看不是 
�
g 的倍数的数是否小于等于 
1
1 个，若是，则 
�
�
�
+
1
ans+1。

代码略。

时间复杂度：
�
(
�
3
)
O(n 
3
 )，期望得分 
20
20 ~ 
40
�
�
�
40pts。

解法二
在解法一的基础上，进行优化。

我们把不是 
�
g 的倍数的数标记成 
1
1 ，把是 
�
g 的倍数的数标记成 
0
0。则问题被转化为求区间和小于等于 
1
1 的区间个数。我们便可在边扫描边处理，当区间和大于 
1
1 时，就退出当前循环。（这种思想最终可以演化为解法四）。

代码略。

或者使用前缀和。（这种思想最终可以演化为解法三）。

#include<cstdio>
int n,g,a[100001],x;
long long ans;
int main(){
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        if(x%g)a[i]=1;
        a[i]+=a[i-1];
    }
    for(int i=1,j;i<n;++i){
        for(j=i+1;j<=n;++j)
            if(a[j]-a[i-1]>1)
                break;
        ans+=j-i-1;
    }
    printf("%lld\n",ans);
    return 0;
}
时间复杂度：
�
(
�
2
)
O(n 
2
 )，期望得分 
40
40 ~ 
70
�
�
�
70pts。

解法三
计 
�
�
a 
i
​
  为数组前 
�
i 个数的前缀和。

在解法二前缀和的基础上进行二分。 找到第一个大于 
�
�
+
1
a 
i
​
 +1 的 
�
�
a 
j
​
  的位置。

#include<cstdio>
int n,g,a[100001],x;
long long ans;
int upper(int l,int r,int x){
    int mid;
    for(;l<=r;){
        mid=(l+r)>>1;
        if(a[mid]<=x)l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        if(x%g)a[i]=1;
        a[i]+=a[i-1];
    }
    for(int i=1;i<n;++i)
        ans+=upper(i+1,n,a[i-1]+1)-i-1;
    printf("%lld\n",ans);
    return 0;
}
时间复杂度：
�
(
�
�
�
�
�
)
O(nlogn)，期望得分 
100
�
�
�
100pts。

解法四
在解法二枚举的基础上用双指针乱搞一波，但也要前缀和。

时间复杂度：
�
(
�
)
O(n)，期望得分 
100
�
�
�
100pts。

代码略。