[YY的GCD](https://www.luogu.org/problemnew/show/P2257)
题意
给你一个n,m，求gcd(i,j)=质数的(x,y)有多少对？(1<=x<=N,1<=y<=M)
思路
题目实际上是要求：
$$
ans=\sum_{i=1}^N\sum_{j=1}^Mgcd(i,j)=prim
$$
由莫比乌斯反演的基本公式：
$$
F(n)=\sum_{n|d}f(d)
$$
$$
f(n)=\sum_{n|d}μ(\frac{d}{n})F(n)
$$
听说一般这种题都是设f(d)= gcd(i,j)==d的个数，F(n) =gcd(i,j)== d和d的倍数的个数 (那么对于上界N和M，就有$F(n)=\lfloor\frac{N}{n}\rfloor \lfloor\frac{M}{n}\rfloor$，因为对于(i,j)，它们的上限为(N,M)，gcd(i,j)=n,而F(n)求的是d和d的倍数的个数，所以对于i，j来说，这样的搭配有N/n*M/n个）。
所以我们可以得到下面的式子：
$$
f(d)=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)==d]
$$
$$
F(n)=\sum_{n|d}f(d) =\lfloor\frac{N}{n}\rfloor \lfloor\frac{M}{n}\rfloor
$$
带入莫比乌斯公式：
$$
f(n)=\sum_{n|d}μ(\frac{d}{n})F(n)=\lfloor\frac{N}{n}\rfloor \lfloor\frac{M}{n}\rfloor\sum_{n|d}μ(\frac{d}{n})
$$
$$
ans=\sum_{i=1}^{N}\sum_{j=1}^{M}[gcd==p]
$$
$$
=\sum_{p=prim}f(p)
$$
$$
=\sum_{p=prim}\sum_{p|d}μ(\frac{d}{p})\lfloor\frac{N}{p}\rfloor \lfloor\frac{M}{p}\rfloor
$$
枚举$\lfloor\frac{d}{p}\rfloor$,或者说令d=dp，那么d就变成了p的倍数，所以sum枚举的值就变成了1~d(d最大可以取到N/p和M/p中的最小值，因为p是gcd(i,j)==p，那么就不可能取i，j中大的值)：
$$
ans=\sum_{p=prim}\sum_{d=1}^{min(\lfloor\frac{N}{p}\rfloor ,\lfloor\frac{M}{p}\rfloor)}μ(d)\lfloor\frac{N}{dp}\rfloor \lfloor\frac{M}{dp}\rfloor
$$
将dp=T，则p∈{t|T%t==0&&t==prim}：
$$
ans=\sum_{T=1}^{min(N,M)}\sum_{t|T,t∈prim}μ(\lfloor\frac{T}{t}\rfloor)\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor
$$
$$
=\sum_{T=1}^{min(N,M)}\lfloor\frac{N}{T}\rfloor\lfloor\frac{M}{T}\rfloor\sum_{t|T,t∈prim}μ(\lfloor\frac{T}{t}\rfloor)
$$
就可以做了。
看！代码
第一份O(n)直接求和的代码，当然会T。
1 |
|
第二份用了整数分块优化，写的我头真大，比如多加一个memset，T，int开了long long T，
1 |
|
POI2007[ZAP-Queries](https://www.luogu.org/problemnew/show/P3455)
题意
求$\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(x,y)=d] $，多组，$1\le d\le a,b\le 50000$
思路
$$ ans=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(x,y)=d] $$我们假设：
$$
f(d)=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(x,y)=d]
$$
$$
F(n)=\sum_{d|n}f(d)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor
$$
$$
f(d)=\sum_{d|n}μ(\lfloor\frac{n}{d}\rfloor)F(n)
$$
发现原来f(d)=ans，那么有：
$$
ans=\sum_{d|n}μ(\lfloor\frac{n}{d}\rfloor)F(n)=\sum_{d|n}μ(\lfloor\frac{n}{d}\rfloor)\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor
$$
枚举$\lfloor{\frac{n}{d}\rfloor}$=t：
$$
ans=\sum_{t=1}^{min(a,b)}μ(t)\lfloor\frac{a}{dt}\rfloor\lfloor\frac{b}{dt}\rfloor
$$
就能做了。
因为前面已经做了一道比这题难的，所以就不写O(n)的写法了，直接上代码，一遍过，爽歪歪。
看！代码
1 |
|
约数个数和
题意
设d(x)为x的约数个数，给定N、M，求$\sum_{i=1}^{N}\sum_{j=1}^{M}d(ij)$
多组，N,M。1<=N, M<=50000
思路
关于这个约数的个数d(x)，它其实有下面这样的函数式：
$$
d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]
$$
接下来套路的设：
$$
f(d)=\sum_{i=1}^N\sum_{j=1}^{M}[gcd(i,j)==d]
$$
$$
F(n)=\sum_{n|d}f(d)=\lfloor\frac{N}{n}\rfloor\lfloor\frac{M}{n}\rfloor –①
$$
由莫比乌斯反演可以得到：
$$
f(n)=\sum_{n|d}μ(\frac{d}{n})F(n)
$$
因为：
$$
ans=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]
$$
由于$∑_{d|n}μ(d)$的性质，即d=1的时候=1，其他都是0，可以将式子化为：
$$
ans=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j} \sum_{d|gcd(x,y)}μ(d)
$$
枚举d|gcd(x,y)的情况 ，d从1取到min(N,M)
$$
ans=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j} \sum_{d=1}^{min(N,M)}μ(d)*[d|gcd(x,y)]
$$
由于μ(d)与x，y，i，j无关，所以可以提到最前面
$$
ans=\sum_{d=1}^{min(N,M)}μ(d) \sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j} [d|gcd(x,y)]
$$
对于x|i，y|j的情况，可以由①得到$=\lfloor\frac{N}{x}\rfloor\lfloor\frac{M}{y}\rfloor$
由枚举i,j和它们的约数改变为枚举它们的约数再直接乘上这些约数的倍数的个数。因为每一个约数都会对它的倍数产生贡献。
$$
c
$$
为了将d|gcd(x,y)这个条件消去，我们更换枚举项x->dx，y->dy：
$$
ans=\sum_{d=1}^{min(N,M)}μ(d) \sum_{x=1}^{\frac{N}{d}}\sum_{y=1}^{\frac{M}{d}}\lfloor\frac{N}{dx}\rfloor\lfloor\frac{M}{dy}\rfloor
$$
$$
ans=\sum_{d=1}^{min(N,M)}μ(d) \sum_{x=1}^{\frac{N}{d}}\lfloor\frac{N}{dx}\rfloor\sum_{y=1}^{\frac{M}{d}}\lfloor\frac{M}{dy}\rfloor
$$
就可以做了。
1 |
|
problem b
题意
- 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
- 输入格式：
第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k - 输出格式：
共n行，每行一个整数表示满足要求的数对(x,y)的个数 - 1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000
思路
这里用了容斥的思想：
$$
ans=\sum_{i=a}^{b}\sum_{j=c}^{d}[gcd(i,j)==k]
$$
实际上，（画个图就明白了）
$$
ans=sum{(1,b)(1,d)}-sum(1,b)(1,c-1)-sum(1,a-1)(1,d)+sum(1,a-1)(1,c-1)
$$
所以还是老套路，ans的每一部分可以分别套入公式算出来，所以只要求出一个公式：
$$
ans=\sum_{t=1}^{min(X,Y)}μ(t)\lfloor\frac{X}{kt}\rfloor\lfloor\frac{Y}{kt}\rfloor
$$
将x、y分别用b、d；b、c-1；a-1、d；a-1，c-1带入公式加加减减就好了。
p.s.现在的题目都T的很。。。无聊。。。我把计算的式子用ans来接收返回的函数然后输出ans,T掉，直接输出结果。。。。就快一点。。话是这样说。。。但是这也太。。。。
1 |
|
crash的数字表格
题意
求$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) $
- 输入格式：
- 输入的第一行包含两个正整数，分别表示N和M。
- 输出格式：
- 输出一个正整数，表示表格中所有数的和mod20101009的值。
思路
由公式：$lcm(i,j)=\frac{ij}{gcd(i,j)}$可以得到，
$$
ans=\sum_{i=1}^{N}\sum_{j=1}^{M}\frac{ij}{gcd(i,j)}
$$
gcd在分母中不好，枚举gcd=d，将其放到前面来：
$$
ans=\sum_{d=1}^{min(N,M)}\sum_{i=1}^{N}\sum_{j=1}^{M}\frac{ij}{d}[gcd(i,j)=d]
$$
d在分母中又不爽，还有gcd，枚举gcd（让i=di，j=dj）：
$$
ans=\sum_{d=1}^{min(N,M)}d\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}ij[gcd(i,j)=1]
$$
由于性质$\sum_{x|n}μ(x) = (n=1)$
$$
ans=\sum_{d=1}^{min(N,M)}d\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}ij \sum_{x|gcd(i,j)}μ(x)
$$
要消去x|gcd(i,j)，因此枚举x：
$$
ans=\sum_{d=1}^{min(N,M)}d\sum_{x=1}^{min(\lfloor\frac{N}{d}\rfloor,\lfloor\frac{M}{d}\rfloor)}μ(x)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}ij[x|gcd(i,j)]
$$
为了消去那个[]的条件，我们让i=xi，j=xj：
$$
ans=\sum_{d=1}^{min(N,M)}d\sum_{x=1}^{min(\lfloor\frac{N}{d}\rfloor,\lfloor\frac{M}{d}\rfloor)}x^2μ(x)\sum_{i=1}^{\lfloor\frac{N}{dx}\rfloor}i\sum_{j=1}^{\lfloor\frac{M}{dx}\rfloor}j
$$