整除问题题解

本题主要考察容斥原理和二维前缀和的应用，是一道较为简单的题目。

20 分的做法

由于 ，我们使用二重循环暴力枚举并去重检查即可，时间复杂度 。

60 分的做法

由于 ，我们可以使用容斥的办法寻找满足要求的数对个数。注意到 ，我们分两步进行容斥。

记 为 中整除 的数字数目，容易得到 。

• 
  因为任何数乘以 2021 都能整除 2021，所以这一步我们可以直接得到 。而在这些数对中， 和 都能整除 2021 的被计数了两次，我们要减掉。所以，满足这个条件的总数为 。
• 
  由于上面已经计数了单个数为 2021 的情况，这一步我们计数仅能被这其中单个因子整除的数，很容易能得到能被 43 但是不能被 47 整除的数的个数为 ，同理可得只能被 47 整除但是不能被 43 整除的数个数为 。根据乘法原理，直接对 b 和 d 分别计算一下然后乘起来即可，即 。

将上述两种容斥结果加起来就是答案了。可以看出，上面的数学计算都是常数且为常数个，所以总复杂度 。

100 分的做法

考虑 60 分的做法，如果我们将 看作一个矩形的左下角，看作一个矩形的右上角的话，我们实际上求出来了在矩形 范围内的点 的个数，其中 。所以，本题被转化为了求矩形 中这样点的个数。我们使用经典的二维前缀和容斥来解决这个问题。

观察上图，我们需要求的点都在 范围内，而 和 根据 60 分的做法我们都可以求出来。这里，我们使用整个矩形的面积减掉 和 的面积，容易得到 ，发现我们多减掉了一个 ，我们将其加回来即可，此时我们就得到了 的面积。

这就是经典的二维前缀和容斥，由于 60 分的做法只需要 的时间做数学计算，这里也是四个简单的数学计算，所以我们在 的时间内就能解决这个问题。

当然，直接对 进行数论容斥也可以解决这个问题，本质和二维前缀和容斥相同，此处不再赘述。

C++ 参考代码如下：

class Solution {
  using ll = long long;

  ll get_43(ll n) {
    ll ans = n / 43;
    ans = ans - ans / 47;
    return ans;
  }

  ll get_47(ll n) {
    ll ans = n / 47;
    ans = ans - ans / 43;
    return ans;
  }

  ll get_2021(ll n) { return n / 2021; }

  ll get(ll n, ll m) {
    ll ans = 0;
    // 43*47
    ans = ans + get_43(n) * get_47(m);
    ans = ans + get_47(n) * get_43(m);

    // 1*2021
    ans = ans + n * get_2021(m);
    ans = ans + m * get_2021(n);
    ans = ans - get_2021(n) * get_2021(m);

    return ans;
  }

public:
  /**
   * 寻找所有能整除 2021 的数对个数
   * @param A long长整型
   * @param B long长整型
   * @param C long长整型
   * @param D long长整型
   * @return long长整型
   */
  long long findPairs(long long A, long long B, long long C, long long D) {
    ll ans = get(B, D);
    ans = ans - get(A - 1, D);
    ans = ans - get(B, C - 1);
    ans = ans + get(A - 1, C - 1);

    return ans;
  }
};