题解 | #整除问题#

题目陈述

给定 a, b, c, d，求所有被 2021 整除的 (x, y) 数对个数，其中 。

算法思路

• 前缀和思想 and 容斥原理（计数问题经常见）

  前缀和思想

• 我们用前缀和的思路来想这个问题,我们要求的是[a,b]和[c,d]中满足条件的数对,如图所示
  

• 计算区间[1,b]和[1,d]满足题目条件的数对个数
  

• 再减去[1,a-1]和[1,d]中满足的，减去[1,b]和[1,c-1]中满足的，

• 容斥原理得，[a-1,c-1]这个区间的数对会被多减去一次，所以要加回来

• 那么我们最后得到的就是[a,b]和[c,d]中满足题目的数对关系了，因为求解两个区间满足条件的数对关系代码一直反复，所以我们可以写一个函数（思路想清楚再打代码，可以减小代码的冗余量以及bug率）

  容斥原理：求解数对关系

• 思路进一步推进，我们的问题已经简化为求解[1,x]和[1,y]中满足题目条件的数对个数
• 我们可以发现2021可以分解为43*47，所以问题就被划分成了一下几步

1. 此处即[1,x]这个区间为A，[1,y]这个区间为B
2. A的因子出2021，B的因子出任意 and A的因子出任意，B的因子出2021，即·x/2021)*y+x*(y/2021)·
3. 两边同时出2021的情况会算两次,减去该情况,即(x/2021)*(y/2021)
4. 计算A出47和B出43的情况,此时单出2021的情况已经被计算过了,即(x/47-x/2021)*(y/43-y/2021)
5. 计算A出43，B出47的情况，(x/43-x/2021)*(y/47-y/2021)

代码实现

C++

typedef long long ll;

class Solution {
public:
    //2021=43*47
    ll cal(ll x,ll y){//计算[1,x]和[1,y]中满足题目条件的数对个数
        //此处即[1,x]这个区间为A，[1,y]这个区间为B
        ll cnt=0;
        cnt+=(x/2021)*y+x*(y/2021);//A的因子出因子2021，B的因子出任意因子 and A的因子出任意因子，B的因子出因子2021
        cnt-=(x/2021)*(y/2021);//上式中，两边同时出2021的情况会算两次，此处减去
        cnt+=(x/47-x/2021)*(y/43-y/2021);//单出2021的情况已经被计算过了，计算A出47和B出43的情况
        cnt+=(x/43-x/2021)*(y/47-y/2021);//计算A出43，B出47的情况
        return cnt;
    }
    long long findPairs(long long a, long long b, long long c, long long d) {
        return cal(b,d)-cal(a-1,d)-cal(b,c-1)+cal(a-1,c-1);
        //计算区间[1,b]和[1,d]满足题目条件的数对个数
        //再减去[1,a-1]和[1,d]中满足的，减去[1,b]中满足的
        //容斥原理得，[a-1,c-1]这个区间会被多减去一次，所以要加回来
    }
};

python

class Solution:
    def findPairs(self , a , b , c , d ):
        return self.cal(b,d)-self.cal(a-1,d)-self.cal(b,c-1)+self.cal(a-1,c-1);
        #计算区间[1,b]和[1,d]满足题目条件的数对个数
        #在减去[1,a-1]和[1,d]中满足的，减去[1,b]中满足的
        #容斥原理得，[a-1,c-1]这个区间会被多减去一次，所以要加回来
    def cal(self ,x,y):
        x=int(x)
        y=int(y)
        cnt=int(0)
        cnt+=(x//2021)*y+x*(y//2021)#A的因子出2021，B的因子出任意 and A的因子出任意，B的因子出2021
        cnt-=(x//2021)*(y//2021)#上式中，两边同时出2021的情况会算两次，此处减去
        cnt+=(x//47-x//2021)*(y//43-y//2021)#单出2021的情况已经被计算过了，计算A出47和B出43的情况
        cnt+=(x//43-x//2021)*(y//47-y//2021)#计算A出43，B出47的情况
        return cnt