题意:
方法一:
暴力枚举(超时)
思路:二重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; } };
时间复杂度:空间复杂度: