CF1475B - 题解

原题链接

  • CodeForces
  • 洛谷

题意

  • 给出 TT 组数据,询问每组数据是否能够被若干个 20202020若干个 20212021 相加组成。

思路

对于题意的一种想法为

num=k1×2020+k2×2021num=(k1+k2)×2021k1num = k_{1} \times 2020 + k_{2} \times 2021 \\ \Rightarrow num = (k_{1} + k_{2}) \times 2021 - k_{1}

则对于给定的数 numnum 如果有方案使得其能够由 k1×2020+k2×2021k_{1} \times 2020 + k_{2} \times 2021 构成,满足:

  • 对于超过 numnum 的与其差最小的 (k1+k2)×2021(k_{1} + k_{2}) \times 2021 的差,记为 Δ=(k1+k2)×2021num\Delta = (k_{1} + k_{2}) \times 2021 - num ,则 Δ(k1+k2)\Delta \leq (k_{1} + k_{2})

于是我们进行判断,符合条件输出 YES,否则输出 NO 即可。

code

#include <cmath>
#include <iostream>
using namespace std;

int T = 0;

inline void solve(const int num) {
  int delta = ceil(num * 1.0 / 2021) * 2021 - num;

  if (delta <= ceil(num * 1.0 / 2021)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> T;

  for (int i = 1, tmp; i <= T; ++i) {
    cin >> tmp;
    solve(tmp);
  }

  return 0;
}