[CSP-S模拟测试]:喝喝喝（模拟）

题目描述

奥利维尔和雪拉扎德在喝酒。
两人连喝$18$瓶后，奥利维尔最终倒下了。
奥利维尔服用了教会研究的醒酒药后，因为服用了太多产生了副作用，第二天睡不着了。
他只好用数数的方式度过无聊的时光，不过他毕竟是皇子，是不会数羊的。他会数数解决小面这个问题：
他先写下一个长度为$n$的数组$a$。一对数组中的数$\{a_x,a_y\}$被称为坏对，当且仅当$x<y$且$a_x\mod a_y=K$。那么有多少个连续子数组不包含坏对呢？

输入格式

一行包含两个整数，$n$和$K$。
第二行包含$n$个整数，表示数组$a$。

输出格式

输出一行包含答案。

样例

样例输入：

3 2
5 3 1

样例输出：

数据范围与提示

样例解释：

$\{5,3\}$是这个数组中唯一一个坏对。

数据范围：

对于$20\%$的数据，$1\leqslant n\leqslant 100$。
对于另外$30\%$的数据，$K=0$。
对于$100\%$的数据，$1\leqslant n\leqslant {10}^5,0\leqslant K\leqslant {10}^5,1\leqslant a_i\leqslant {10}^5$

题解

发现对于一个左端点，其合法区间的右端点一定是一个连续的段，而不能是断断续续的。

所以我们考虑维护合法区间。

$a_x\mod a_y=K$即为$(a_x-K)\mod a_y=0$。

那么我们可以将$a_x-K$分解质因数即可。

时间复杂度：$\Theta(n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

long long n,K,ans;

long long a[100001];

long long cnt[100001];

int main()

{

	memset(cnt,0x3f,sizeof(cnt));

	scanf("%lld%lld",&n,&K);

	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

	long long lft=n,rht=n+1;

	for(int i=n;i;i--)

	{

		if(a[i]==K)rht=min(lft,rht);

		else

			for(int j=1;j*j<=a[i]-K;j++)

			{

				if((a[i]-K)%j)continue;

				if(j>K)rht=min(cnt[j],rht);

				if((a[i]-K)/j>K)rht=min(cnt[(a[i]-K)/j],rht);

			}

		if(a[i]>K)lft=i;

		cnt[a[i]]=i;

		ans+=rht-i;

	}

	printf("%lld",ans);

	return 0;

}

rp++

巴特西