自动搬运

查看原文

来自洛谷，原作者为

	ShineEternal **

搬运于2025-08-24 22:11:22，当前版本为作者最后更新于2019-08-09 21:33:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接：

https://www.luogu.org/problem/P5497

分析：

我们如果看一眼题面却没有头绪不妨看一眼数据，一看到$10^{18}$，我们就大概能猜到这是一道重在思维的规律题。

首先此题不要误认为是1~n的正整数序列（也就只有我这么想？）然后我们就只能被逼的走投无路寻找内在的关系

此时我们连前缀和数组也根本无法使用，但在模拟小数据时可以发现以下性质：

• 如果一个数%m不为0，则可能有$m-1$种取值

• 而如果序列中超过了m-1个数，就一定有两个数%m取值相同

那么我们设前缀和为$s[i]$（此数组实际无法求得）

这时候就可以把前缀和看成一个序列

如果这个序列长度超过$m-1$，那么就必有两个数%m相等

上面这一条应该不难证明，限于篇幅原因不详细叙述，可以来参考这篇blog，是我之前的一篇没过的日报，所以大神就不用进去了QAQ

这两个数%m相等，设为$s[i],s[j](i>j)$,即$s[i]$ $mod$ $m=s[j]$ $mod$ $m$

所以(s[i]-s[j])%m==0

即为j~i区间的和是题目所求的

于是问题就简单了，序列长度n>m-1,即n>=m，则YES，否则NO

code：

#include<cstdio>
using namespace std;
int main()
{
	long long n,m;
	scanf("%lld%lld",&n,&m);
	if(n>=m)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

求过求赞喔