题意:


方法一:
暴力枚举(超时)

思路:二重for循环,如果x*y能被2021整除,则加一。


#define ll long long 

class Solution {
public:
    
    long long findPairs(long long a, long long b, long long c, long long d) {
        ll res=0;
        for(ll x=a;x<=b;x++){//二重for循环
            for(ll y=c;y<=d;y++){
                if(x*y%2021==0){//如果x*y能被2021整除,则加一
                    res++;
                }
            }
        }
        return res;
    }

时间复杂度:
空间复杂度:
方法二:
容斥原理

思路:
通过计算可知2021只有  1  ,  43  ,  47  ,  2021  四个因子。
那么等效于
因此有两种情况:
(1)
x含有因子43,y含有因子47
x含有因子47,y含有因子43。
(2)
x含有因子43和47,y不含有因子43和47

y含有因子43和47,x不含有因子43和47

#define ll long long 

class Solution {
public:
    
    long long findPairs(long long a, long long b, long long c, long long d) {
        
        ll res=0,n=b-a+1,m=d-c+1;//n,m分别是[a,b],[c,d]区间个数
        res+=f(a,b,43)*f(c,d,47);//x含有因子43,y含有因子47
        res+=f(a,b,47)*f(c,d,43);//x含有因子47,y含有因子43
        res-=f(a,b,2021)*f(c,d,2021);//减去交集部分
        res+=f(a,b,2021)*(m-f(c,d,47)-f(c,d,43)+f(c,d,2021));//x含有因子43和47,y不含有因子43和47
        res+=f(c,d,2021)*(n-f(a,b,47)-f(a,b,43)+f(a,b,2021));//y含有因子43和47,x不含有因子43和47
        return res;
    }
    ll f(int l,int r,int x){//[l,r]区间内x的倍数的个数
        return r/x-(l-1)/x;
    }
    
};


时间复杂度:
空间复杂度: