自动搬运

查看原文

来自洛谷，原作者为

	翟翟 我在黄昏垂钓太阳。试图拉起我堕落的人生。

搬运于2025-08-24 22:42:42，当前版本为作者最后更新于2023-01-17 12:00:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法一

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

代码略。

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

解法二

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

我们把不是 $g$ 的倍数的数标记成 $1$ ，把是 $g$ 的倍数的数标记成 $0$。则问题被转化为求区间和小于等于 $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;
}

时间复杂度：$\mathcal O(n^2)$，期望得分 $40$ ~ $70 pts$。

解法三

计 $a_i$ 为数组前 $i$ 个数的前缀和。

在解法二前缀和的基础上进行二分。 找到第一个大于 $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;
}

时间复杂度：$\mathcal O(n log n)$，期望得分 $100 pts$。

解法四

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

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

代码略。