526互联

Codeforces Round 697 (Div. 3) B. New Year's Number

发布时间 2023-10-12 15:15:29作者: zsxuan

给出一个数 \(n\) ，询问能否存在 \(2020x + 2021y = n\) 。

对于方程 \(ax + by = n\) 可以直接解 \(exgcd\) 查询是否有解。

观察到 \(2020x + 2021y = n\) 可以化为 \(2020(x + y) + y = n\) 。不妨定为 \(2020x' + y' = n\) 。

\(ax + y = n\) 可以直接得到 \(y \equiv r\ (\mod x)\) 得到 \(x\) 的通解。于是可以解出某组 \(x, y\) 的解。

只需解出一组 \(x', y'\) 使 \(x' \geq y'\) 即可。

显然解出最小的 \(y' = r\) ，若 \(r \leq \frac{n - r}{2020}\) 则有解。

view 
#include <bits/stdc++.h>
void solve(){
	int n; std::cin >> n;
	// 2020(x + y) + y = n
	// 2020x' + y' = n
	int y = n % 2020;
	int x = (n - y) / 2020;
	std::cout << (y <= x ? "YES" : "NO") << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}