题解 | #整除问题#
整除问题
http://www.nowcoder.com/practice/d7a0bdf03ea0468ea75f28bd36344d18
题意：
方法一：
暴力枚举（超时）
思路：二重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;
}
时间复杂度：%2Cn%E6%98%AF%E9%81%8D%E5%8E%86%E5%8C%BA%E9%97%B4%E9%95%BF%E5%BA%A6%E3%80%82)
空间复杂度：%2C%E7%A9%BA%E9%97%B4%E6%97%A0%E5%AD%98%E5%82%A8)
方法二：
容斥原理
思路：通过计算可知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;
}
};
时间复杂度：%2C%E5%B8%B8%E9%87%8F%E7%BA%A7%E5%88%AB)
空间复杂度：
查看7道真题和解析
