题解 P5497 【[LnOI2019SP]龟速单项式变换(SMT)】

皎月半洒花

2019-08-09 20:53:09

题解

其实是一道水题，以下是证明：

求证

\forall k\in\mathbb{N+},m|\sum_{i=0}^{n-1}(k+i)\Longleftrightarrow m\leq n

我们把和式展开成为：

nk+\frac{n(n-1)}{2}

这个东西是m的倍数，+连接说明应有m|nk。而k是任意的，所以要有m|n，即n\mod m=0。

而因为本题的坑点在于选的是连续子序列，所以只需要n\geq m，就\exists i\leq n~s.t.i\mod m = 0

#include <cstdio>
#include <iostream>

#define LL long long

using namespace std ;
LL N, M ;

int main(){
    cin >> N >> M ;
    if (M > N) puts("NO") ; else puts("YES") ;
}