题解 P5497 【[LnOI2019SP]龟速单项式变换(SMT)】
ShineEternal
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](https://45475.blog.luogu.org/luo-gu-ri-bao),是我之前的一篇没过的日报,所以大神就不用进去了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:
```cpp
#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;
}
```
求过求赞喔