洛谷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;
}