定义和常用公式
1
2
\([p]=(p?1:0)\)
\(\epsilon(x)=[x=1]\)
\(id(x)=x\)
\(I(x)=1\)
\(\varphi(x)=\sum_{i=1}^x [gcd(i,x)=1]\)
\(d(x)=\sum_{d|x}1\)
3
4
\(\sum_{i=1}^{n}\sum_{j=1}^m[gcd(i,j)=1]\)
\(=\sum_{i=1}^{n}\sum_{j=1}^m\epsilon(gcd(i,j))\)
\(=\sum_{i=1}^{n}\sum_{j=1}^m\sum_{d|gcd(i,j)}\mu(d)\)
\(=\sum_{d=1}^{min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(d)\)
\(=\sum_{d=1}^{min(n,m)}\mu(d)(n/d)(m/d)\)
5
当公式4中\(n=m\)时，有
\(\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]\)
\(=\sum_{1\leq i,j\leq n}[gcd(i,j)=1]\)
\(=\sum_{1\leq i\leq j\leq n}[gcd(i,j)=1]+\sum_{1\leq j\leq i\leq n}[gcd(i,j)=1]-\sum_{1\leq i=j\leq n}[gcd(i,j)=1]\)
\(=2\sum_{1\leq i\leq j\leq n}[gcd(i,j)=1]-1\)
\(=2\sum_{1\leq j\leq n}\sum_{1\leq i\leq j}[gcd(i,j)=1]-1\)
\(=2\sum_{1\leq j\leq n}\varphi(j)-1\)
\(=2\sum_{j=1}^n\varphi(j)-1\)
常用模板
线性筛
整除分块
例题
luoguP1390
\(\sum_{i=1}^{n}\sum_{j=i+1}^{n}gcd(i,j)\)
\(=\sum_{i}\sum_{j}\sum_{k}k[k=gcd(i,j)][1\leq i<j\leq n]\)
\(=\sum_{k}k\sum_{i}\sum_{j}[k=gcd(i,j)][1\leq i<j\leq n]\)
\(=\sum_{k}k\sum_{i}\sum_{j}[gcd(i,j)=1][1\leq i<j\leq n/k]\)
\(=\sum_{k}k\sum_{j=1}^{n/k}\sum_{i=1}^{j-1}[gcd(i,j)=1]\)
\(=\sum_{k}k\sum_{j=1}^{n/k}(\varphi(j)-[gcd(j,j)=1])\)
\(=\sum_{k}k(-1+\sum_{j=1}^{n/k}\varphi(j))\)
线性筛+前缀和
\(O(n)\)
luoguP2398
\(\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\)
\(=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nk[k=gcd(i,j)]\)
\(=\sum_{k=1}^nk\sum_{i=1}^{n/k}\sum_{j=1}^{n/k}[gcd(i,j)=1]\)
\(=\sum_{k=1}^nk\sum_{d=1}^{n/k}\mu(d)(n/k/d)(n/k/d)\)(由公式4)
\(=\sum_{k=1}^n\sum_{d|k}(k/d)\mu(d)(n/k)(n/k)\)
\(=\sum_{k=1}^n(n/k)(n/k)\sum_{d|k}(k/d)\mu(d)\)
\(=\sum_{k=1}^n(n/k)(n/k)\varphi(k)\)
或
\(\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\)
\(=\sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\varphi(d)\)
\(=\sum_{d}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\varphi(d)\)
\(=\sum_{d}(n/d)(n/d)\varphi(d)\)
线性筛即可
复杂度\(O(n)\)
luoguP2257
\(\sum_{p}\sum_{i=1}^N\sum_{j=1}^M[p=gcd(i,j)]\)
\(=\sum_{p}\sum_{d=1}^{min(n/p,m/p)}\mu(d)(n/p/d)(m/p/d)\)(由P2398)
\(=\sum_{k}\sum_{p|k}\mu(k/p)(n/k)(m/k)\)
\(=\sum_{k}(n/k)(m/k)\sum_{p|k}\mu(k/p)\)
\(=\sum_{k}(n/k)(m/k)f(k)\)
其中\(f(x)=\sum_{p|x}\mu(x/p)\)
\(f\)可通过枚举所有素数，枚举它们的倍数做到\(O(n\log\log n)\)
也可由线性筛(\(f(px)=mu(x)-f(x)\))\(O(n)\)求出
然后进行整除分块
总复杂度\(O(n+T\sqrt{n})\)
luoguP2568
P2257中取\(N=M\)即可,但此题时间限制为P2257的\(\frac{1}{4}\)
或
\(\sum_{p}\sum_{i=1}^n\sum_{j=1}^n[p=gcd(i,j)]\)
\(=\sum_{p}\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}[gcd(i,j)=1]\)
\(=\sum_{p}(2\sum_{j=1}^{n/p}\varphi(j)-1)\)
线性筛+前缀和即可
复杂度\(O(n)\)
luoguP3327
先推导一个关于\(d(ij)\)的公式
设
\(i=p_1^{a_1}p_2^{a_2}p_3^{a_3}...\)
\(j=p_1^{b_1}p_2^{b_2}p_3^{b_3}...\)
又设\(X\)为\(i\)的因数，\(Y\)为\(j\)的因数
\(X=p_1^{x_1}p_2^{x_2}p_3^{x_3}...\)
\(Y=p_1^{y_1}p_2^{y_2}p_3^{y_3}...\)
则\(\frac{jX}{Y}=p_1^{x_1+b_1-y_1}p_2^{x_2+b_2-y_2}p_3^{x_3+b_3-y_3}...\)对于任意的\(i\)：
当\(x_i=0,y_i>0\)时，\(x_i+b_i-y_i\)取\(0\)到\(b_i-1\)的所有值；
当\(x_i=0,y_i=0\)时，\(x_i+b_i-y_i\)取\(b_i\)；
当\(x_i>0,y_i=0\)时，\(x_i+b_i-y_i\)取\(1+b_i\)到\(a_i+b_i\)的所有值；
所以当\(\forall i,\min(x_i,y_i)=0\)即\(gcd(X,Y)=1\)时，\(\{\frac{jX}{Y}\}\)为\(ij\)的所有因数
所以得到下式：
下面看题
\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\)
\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)
\(=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{n/x}\sum_{j=1}^{m/y}[gcd(x,y)=1]\)
\(=\sum_{x=1}^{n}\sum_{y=1}^{m}(n/x)(m/y)[gcd(x,y)=1]\)
\(=\sum_{x=1}^{n}\sum_{y=1}^{m}(n/x)(m/y)\sum_{d|gcd(x,y)}\mu(d)\)
\(=\sum_{d=1}^{\min(m,n)} \sum_{x=1}^{n/d}\sum_{y=1}^{m/d}(n/(xd))(m/(yd))\mu(d)\)
\(=\sum_{d=1}^{\min(m,n)} \mu(d) (\sum_{x=1}^{n/d}(n/d)/x) (\sum_{y=1}^{m/d}(m/d)/y)\)
\(=\sum_{d=1}^{\min(m,n)} \mu(d) (\sum_{k=1}^{n/d}(n/d)/k) (\sum_{k=1}^{m/d}(m/d)/k)\)
\(=\sum_{d=1}^{\min(m,n)} \mu(d) f(n/d) f(m/d)\)
其中\(f(x)=\sum_{k=1}^{x}x/k\)，可\(O(n)\)预处理
再用线性筛\(O(n)\)求出\(\mu\)的前缀和
整除分块即可
\(O(n+T\sqrt{n})\)
luoguP2522
类似二维前缀和
\(\sum_{x=a}^{b}\sum_{y=c}^{d}[gcd(x,y)=k]\)
\(=\sum_{x=a}^{b}(\sum_{y=1}^{d}[gcd(x,y)=k]-\sum_{y=1}^{c-1}[gcd(x,y)=k])\)
\(=\sum_{x=a}^{b}\sum_{y=1}^{d}[gcd(x,y)=k]-\sum_{x=a}^{b}\sum_{y=1}^{c-1}[gcd(x,y)=k]\)
\(=\sum_{y=1}^{d}\sum_{x=a}^{b}[gcd(x,y)=k]-\sum_{y=1}^{c-1}\sum_{x=a}^{b}[gcd(x,y)=k]\)
\(=\sum_{y=1}^{d}(\sum_{x=1}^{b}[gcd(x,y)=k]-\sum_{x=1}^{a-1}[gcd(x,y)=k])-\sum_{y=1}^{c-1}(\sum_{x=1}^{b}[gcd(x,y)=k]-\sum_{x=1}^{a-1}[gcd(x,y)=k])\)
\(=\sum_{y=1}^{d}\sum_{x=1}^{b}[gcd(x,y)=k]-\sum_{y=1}^{d}\sum_{x=1}^{a-1}[gcd(x,y)=k]-\sum_{y=1}^{c-1}\sum_{x=1}^{b}[gcd(x,y)=k]+\sum_{y=1}^{c-1}\sum_{x=1}^{a-1}[gcd(x,y)=k])\)
\(=s[b][d]-s[a-1][d]-s[b][c-1]+s[a-1][c-1]\)
其中
\(s[n][m]\)
\(=\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=k]\)
\(=\sum_{x=1}^{n/k}\sum_{y=1}^{m/k}[gcd(x,y)=1]\)
\(=\sum_{d=1}^{min(n/k,m/k)}\mu(d)(n/k/d)(m/k/d)\)
线性筛+整除分块
复杂度\(O(n+T\sqrt n)\)
luoguP3768
\(\sum_{i=1}^{n}\sum_{j=1}^{n}ijgcd(i,j) \pmod p\)
\(\equiv \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k}ijk[k=gcd(i,j)] \pmod p\)
\(\equiv \sum_{k}\sum_{i=1}^{n/k}\sum_{j=1}^{n/k}ijk^3[gcd(i,j)=1] \pmod p\)
\(\equiv \sum_{k}k^3\sum_{i=1}^{n/k}\sum_{j=1}^{n/k}ij[gcd(i,j)=1] \pmod p\)
\(\equiv \sum_{k}k^3\sum_{i=1}^{n/k}\sum_{j=1}^{n/k}ij\sum_{d|gcd(i,j)}\mu(d) \pmod p\)
\(\equiv \sum_{k}k^3\sum_{d}\sum_{i=1}^{n/k/d}\sum_{j=1}^{n/k/d}ijd^2\mu(d) \pmod p\)
\(\equiv \sum_{k}k^3\sum_{d}d^2\mu(d)\sum_{i=1}^{n/k/d}i\sum_{j=1}^{n/k/d}j \pmod p\)
\(\equiv \sum_{k}k^3\sum_{d}d^2\mu(d)((\sum_{i=1}^{n/k/d}i)(\sum_{j=1}^{n/k/d}j)) \pmod p\)
\(\equiv \sum_{k}k^3\sum_{d}d^2\mu(d)s[n/k/d]^2 \pmod p\)
后面要用杜教筛 等我学会了再接着写