网站开发的开发工具,网站需要第三方登录怎么做,穆棱seo,烟台h5网站建设P3327 约数的个数和
题意 d(x)d(x)d(x)为约数的个数,对于每个询问,回答∑i1n∑j1md(ij)\sum_{i1}^n\sum_{j1}^md(ij)∑i1n∑j1md(ij).
题解
这个题推得我头皮发麻,然后还没推出来,后来发现要做这题的先知道一个性质: d(ij)∑x∣i∑y∣j[gcd(x,y)1]d(ij)\sum_{x|i}\sum_{…P3327 约数的个数和
题意
d(x)d(x)d(x)为约数的个数,对于每个询问,回答∑i1n∑j1md(ij)\sum_{i1}^n\sum_{j1}^md(ij)∑i1n∑j1md(ij).
题解
这个题推得我头皮发麻,然后还没推出来,后来发现要做这题的先知道一个性质:
d(ij)∑x∣i∑y∣j[gcd(x,y)1]d(ij)\sum_{x|i}\sum_{y|j}[gcd(x,y)1]d(ij)∑x∣i∑y∣j[gcd(x,y)1]
通过这个性质,我们把原式写成 ∑i1n∑j1m∑x∣i∑y∣j[gcd(x,y)1]\sum_{i1}^n\sum_{j1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)1]∑i1n∑j1m∑x∣i∑y∣j[gcd(x,y)1]
我们知道∑d∣xμ(d)[x1]\sum_{d|x}\mu(d)[x1]∑d∣xμ(d)[x1],代换进去,就得到了:
∑i1n∑j1m∑x∣i∑y∣j∑d∣gcd(x,y)μ(d)\sum_{i1}^n\sum_{j1}^m\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)∑i1n∑j1m∑x∣i∑y∣j∑d∣gcd(x,y)μ(d)
变枚举i,ji,ji,j为枚举x,yx,yx,y:
∑x1n∑y1m⌊nx⌋⌊my⌋∑d∣gcd(x,y)μ(d)\sum_{x1}^n\sum_{y1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor\sum_{d|gcd(x,y)}\mu(d)∑x1n∑y1m⌊xn⌋⌊ym⌋∑d∣gcd(x,y)μ(d)
再转为枚举ddd,得到:
∑d1μ(d)∑x1n/d∑y1m/d⌊nxd⌋⌊myd⌋\sum_{d1}\mu(d)\sum_{x1}^{n/d}\sum_{y1}^{m/d} \lfloor \frac{n}{xd} \rfloor \lfloor \frac{m}{yd} \rfloor∑d1μ(d)∑x1n/d∑y1m/d⌊xdn⌋⌊ydm⌋
也即
∑d1μ(d)(∑x1n/d⌊nxd⌋)(∑y1m/d⌊myd⌋)\sum_{d1}\mu(d)(\sum_{x1}^{n/d} \lfloor \frac{n}{xd} \rfloor) (\sum_{y1}^{m/d} \lfloor \frac{m}{yd} \rfloor)∑d1μ(d)(∑x1n/d⌊xdn⌋)(∑y1m/d⌊ydm⌋)
记f(x)∑i1x⌊xi⌋f(x)\sum_{i1}^x \lfloor \frac{x}{i} \rfloorf(x)∑i1x⌊ix⌋,则原式:
∑d1μ(d)f(⌊nd⌋)f(⌊md⌋)\sum_{d1}\mu(d)f(\lfloor \frac{n}{d} \rfloor)f(\lfloor \frac{m}{d} \rfloor)∑d1μ(d)f(⌊dn⌋)f(⌊dm⌋)
若f(x)f(x)f(x)可以O(1)O(1)O(1)查询的话,上面的式子就可以O(n)O(\sqrt{n})O(n)数论分块求出.
显然,f(x)f(x)f(x)可以用O(nn)O(n\sqrt{n})O(nn)的时间复杂度预处理出来,方法也是数论分块.
代码
// luogu-judger-enable-o2
#include iostream
#include algorithm
#include cstring
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
typedef long long LL;
const int N 50010;
int n,m,T;
int prime[N10],mu[N10],pcnt,zhi[N10],low[N10];
void sieve() {mu[1] zhi[1] 1;for(int i 2;i N;i) {if(!zhi[i]) {prime[pcnt] i;mu[i] -1;}for(int j 0;j pcnt i * prime[j] N;j) {zhi[i*prime[j]] 1;if(i % prime[j] 0) {mu[i*prime[j]] 0;break;}else{mu[i*prime[j]] -mu[i];}}}
}
LL F[N10];
int main() {std::ios::sync_with_stdio(false);std::cin T;sieve();for(int i 1;i N;i) {mu[i] mu[i-1];}for(int i 1;i N;i) {for(int x 1,last;x i;x last1) {last i/(i/x);F[i] (last-x1)*(i/x);}}while(T--) {std::cin n m;LL ans 0;int lim n m?m:n;for(int x 1,nx1,nx2,nxt;x lim;x nxt1) {nx1 n/(n/x);nx2 m/(m/x);nxt nx1nx2?nx2:nx1;ans (mu[nxt]-mu[x-1])*F[n/x]*F[m/x];}std::cout ans std::endl;}return 0;
}
