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

题目链接：P5497 [LnOI2019SP] 龟速单项式变换(SMT)

题意：

若正整数序列 $a$ 中存在连续若干个正整数的和为 $m$ 的倍数，则这个正整数序列 $a$ 被称为“$m$ 序列”。

给定 $n$ 和 $m$，你需要知道长度为 $n$ 的任意正整数序列 $a$ 是否都是“$m$ 序列”。

输入格式：

两个数，$n$ 和 $m$。

输出格式：

如果成立输出 YES 否则输出 NO。

数据范围：

$1 \le n, m \le {10}^{18}$。

显然 $n < m$ 时构造 $[1,1,\cdots,1]$ 即可。

当 $n \ge m$ 时，记 $S_i = \sum_{1 \le j \le i}a_j$ ，则至少存在一对 $(l,r)$ 满足 $S_l\equiv S_r\pmod{m}$

又因为他们的差一定不为 $0$ ，则区间 $[l+1,r]$ 的和是 $m$ 的倍数，即 $n \ge m$​ 时不存在非法构造。

因此这道题只需要判断一下 $n,m$ 的大小关系即可。

时间复杂度 $\mathcal{O}(1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    cout << (n >= m ? "YES" : "NO") << '\n';
    return 0;
}