对于给出的 \(n\) 个询问,每次求有多少个数对 \((x,y)\),满足 \(a≤x≤b,c≤y≤d\),且 \(\text{gcd}(x,y) = k\),\(\text{gcd}(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。
第一行一个整数 \(n\)。
接下来 \(n\) 行每行五个整数,分别表示 \(a、b、c、d、k\)。
共 \(n\) 行,每行一个整数表示满足要求的数对 \((x,y)\) 的个数。
\(1 \le n \le 50000\),
\(1 \le a \le b \le 50000\),
\(1 \le c \le d \le 50000\),
\(1 \le k \le 50000\)
2 2 5 1 5 1 1 5 1 5 2
14 3
莫比乌斯反演
本题单用容斥原理和莫比乌斯函数也可做:215. 破译密码
这里介绍莫比乌斯反演做法
先给出莫比乌斯函数的一个性质:\(\sum_{d \mid n} \mu(d)= \begin{cases}1 & n=1 \\ 0 & n \neq 1\end{cases}\) 。简略证明:\(n=1\) 时显然。当 \(n>1\) 时,对 \(n\) 分解质因数:\(n=\prod_{i=1}^{k} p_{i}^{c_{i}}\),当存在 \(c_i>1\) 时该项表示的约数的 \(d\) 的 \(\mu(d)=0\),这种情况的约数不考虑,即只用考虑 \(\prod_{i=1}^{k} p_{i}\) 的约数,即在这 \(k\) 个数中选出 \(1\) 个数组成约数,\(2\) 组成约数,\(3\) 个数组成约数,\(\dots\),组成 \(k\) 个数组成约数,由莫比乌斯函数,奇数种质数为 \(-1\),偶数种质数为 \(1\),则 \(\sum_{d \mid n} \mu(d)=\sum_{i=0}^{k} C_{k}^{i} \cdot(-1)^{i}=(1+(-1))^{k}=0\)
接着,有莫比乌斯反演的两条重要定理:
如果有 \(F(n)=\sum_{d \mid n} f(d)\) ,那么有 \(f(n)=\sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right)\)
证明:将 \(F(n)=\sum_{d \mid n} f(d)\) 代入,得 \(\sum_{d \mid n} \mu(d) \sum_{i\mid \frac{n}{d}}f[i]\),观察 \(i\) 和 \(d\) 配对的情况,当 \(d=1\) 时 \(i\) 取遍 \(n\) 的约数,而对于某个固定的 \(i\),要求找出与 \(i\) 配对的 \(d\),这样的 \(d\) 需满足:\(d\mid n,i\mid \frac{n}{d}\),即 \(d\mid \frac{n}{i}\),此时可以交换 \(i,d\) 顺序,即:\(\sum_{i \mid n} f(i) \sum_{d\mid \frac{n}{i}}\mu(d)\),由莫比乌斯函数约数和性质,当且仅当 \(i=n\) 时后面的和不为 \(0\),即\(\sum_{i \mid n} f(i) \sum_{d\mid \frac{n}{i}}\mu(d)=f(n)\)
如果有 \(F(n)=\sum_{n \mid d} f(d)\) ,那么有 \(f(n)=\sum_{n \mid d} \mu\left(\frac{d}{n}\right) F(d)\)
同理。这条定理常用。
本题按前缀和可转化为求解:\(\sum_{i=1}^{a} \sum_{j=1}^{b}[(i, j)=n]\),其中 \((i,j)\) 表示 \(i\) 和 \(j\) 的最大公约数
由莫比乌斯反演的性质,求解 \(F(n)\) 容易,求解 \(f(n)\) 困难,本题中 \(f(n)=\sum_{i=1}^{a} \sum_{j=1}^{b}[(i, j)=n]\),而由莫比乌斯反演第二条定理,可设定 \(F(n)=\sum_{i=1}^{a} \sum_{j=1}^{b}[n\mid (i, j)]\),其含义表示的是 \(x\in [1,a],y\in [1,b]\) 中 \(gcd(x,y)\) 是 \(n\) 的倍数的点数,\([1,a]\) 中有 \(a/n\) 个值是 \(n\) 的倍数,\([1,b]\) 中有 \(b/n\) 个值是 \(n\) 的倍数,由乘法原理,共有 \((a/n)\times (b/n)\) 个点满足要求,即 \(F(n)=(a/n)\times (b/n)\),则 $f(n)=\sum_{n \mid d} \mu\left(\frac{d}{n}\right)(a/d)\times (b/d) $,令 \(d'=\frac{d}{n}\),则 $f(n)=\sum_{d'} \mu(d')(a/d'n)\times (b/d'n) $,而倍数 \(d'\) 也不能无限大,$(d')(a/d'n)\times (b/d'n) $ 导致 \(d'\) 最大为 \(n=min(a/n,b/n)\),令 \(a=a/n,b=b/n\),即 $f(n)=\sum_{i=1}^n\mu(i)(a/i)\times (b/i) $,此时转化为单靠容斥原理得到的结论
// Problem: problem b // Contest: AcWing // URL: https://www.acwing.com/problem/content/2704/ // Memory Limit: 64 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=5e4+5; int q,a,b,c,d,k,m,prime[N],v[N],u[N],s[N]; void primes(int n) { u[1]=1; for(int i=2;i<=n;i++) { if(v[i]==0) { u[i]=-1; v[i]=prime[++m]=i; } for(int j=1;prime[j]*i<=n&&j<=m;j++) { if(v[i]<prime[j])break; if(i%prime[j]==0) u[i*prime[j]]=0; else u[i*prime[j]]=-u[i]; v[i*prime[j]]=prime[j]; } } for(int i=1;i<=n;i++)s[i]=s[i-1]+u[i]; } int g(int a,int b) { return a/(a/b); } LL f(int a,int b,int d) { LL res=0; a/=d,b/=d; int n=min(a,b); for(int l=1,r;l<=n;l=r+1) { r=min({n,g(a,l),g(b,l)}); res+=1ll*(s[r]-s[l-1])*(a/l)*(b/l); } return res; } int main() { primes(N-1); cin>>q; while(q--) { cin>>a>>b>>c>>d>>k; cout<<f(b,d,k)-f(b,c-1,k)-f(a-1,d,k)+f(a-1,c-1,k)<<'\n'; } return 0; }