一、莫比乌斯
1、莫比乌斯函数:\(u(n)=\left\{\begin{array}{l} 1\qquad \qquad n=1 \\ 0\qquad \qquad n含有平方因子 \\ (-1)^{k} \qquad n里面所包含质因子数目 \end{array}\right.\)
令 \(\varepsilon(n) = \sum_{d|n}^{n}u(d)=[n=1]\),那么我们有 \(\varepsilon = u \ * \ 1\) ,当 \(n=1\) 时,\(\varepsilon (1) = 1\),否则 \(\varepsilon (n) = 0\)。
定义:莫比乌斯是一个积性函数,积性函数乘以一个积性函数得到的函数也是一个积性函数,满足 \(h(x)=f(x)g(x)\),另外也有如果\(gcd(n,m)=1\),\(h(nm)=h(n)h(m)\) 。
此外完全积性函数满足任意的 \(h(nm)=h(n)h(m)\) 。
另外也有 \([gcd(i,j)=1]=\sum_{d|gcd(i,j)}u(d)=\varepsilon(gcd(i,j))\) 。
代码:线性筛预处理每个数的莫比乌斯函数值 \(O(n)\)
template<typename T>
struct Mu{
int N;
vector<T> preim;
vector<T> a, mu;
Mu(int N_) : a(N_ + 1), mu(N_ + 1) {
N = N_;
mu[1] = 1;
for (T i = 2; i <= N; i++) {
if (!a[i]) {
a[i] = i;
preim.push_back(i);
mu[i] = -1;
}
for (auto p : preim) {
if (1LL * i * p > N) continue;
a[i * p] = p;
if (i % p == 0) {
break;
}
mu[i * p] = -mu[i];
}
}
}
};
2、扩展积性函数:
\(\varphi * 1=id\)
然后我们可以发现,我们对等式两边同时卷积 \(u\) ,得到 \(\varphi * 1 * u=id*u\Rightarrow \varphi*\varepsilon =id*u\Rightarrow\varphi=id*u\) 。
因此可以得到:\(\varphi(n)=\sum_{d|n}d·u(\frac{n}{d})\) 。
通常如果一个函数满足积性函数的性质,那么我们就能在线性筛的过程中 \(O(n)\) 的求出所有的函数值。
3、莫比乌斯变换:
\((1)\) :形式一:如果有 \(f(n)=\sum_{d|n}g(d)\),那么有 \(g(n)=\sum_{d|n}f(d)u(\frac{n}{d})\) 。
\((2)\) :形式二:如果有 \(f(n)=\sum_{n|d}g(d)\),那么有 \(g(n)=\sum_{n|d}f(d)u(\frac{d}{n})\) 。
通常情况下第二种形式常用。
4、有一些做题出现的常见的式子:
\((1)\):\(\sum_{i=x}^{n}\sum_{j=y}^{m}[gcd(i,j)=k]\qquad (1 \le T,x,y,n,m,k\le 5e4)\) 。
我们令 \(f(x,n,y,m)=\sum_{i=x}^{n}\sum_{j=y}^{m}[gcd(i,j)=k]\qquad (1 \le T,x,y,n,m,k\le 5e4)\),那么我们可以由容斥定理得:\(f(x,n,y,m)=f(1,n,1,m)-f(1,x-1,1,m)-f(1,n,1,y-1)+f(1,x-1,1,y-1)\),所以相当于分为四个部分进行处理 。
\(\Rightarrow \sum_{i=1}^{\frac{n}{k}}\sum_{i=1}^{\frac{m}{k}}[gcd(i,j)=1]\)
\(\Rightarrow \sum_{i=1}^{\frac{n}{k}}\sum_{i=1}^{\frac{m}{k}}\sum_{d|gcd(i,j)}u(d)\)
\(\Rightarrow \sum_{d=1}^{\frac{min(n,m)}{k}}u(d)\sum_{i=1}^{\frac{n}{k}}[d\ |\ i]\sum_{i=1}^{\frac{m}{k}}[d\ |\ j]\)
\(\Rightarrow \sum_{d=1}^{\frac{min(n,m)}{k}}u(d)\left \lfloor \frac{n}{dk} \right \rfloor\left \lfloor \frac{m}{dk} \right \rfloor\)
然后就可以把上面的公式套入这里面,得到答案。
时间复杂度为:\(O(T\sqrt{n})\) 。
\((2)\):\(\sum_{i=1}^{n}lcm(i,n)\qquad 1\le T\le 3e5,1\le n\le1e6\) 。
\(\Rightarrow \sum_{i=1}^{n}\frac{in}{gcd(i,n)}\)
\(\Rightarrow n\sum_{d|n}\frac{1}{d}\sum_{i=1}^{n}i[gcd(i,n)=d]\)
\(\Rightarrow n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})=1]\)
\(\Rightarrow n\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i\sum_{k|gcd(i,\frac{n}{d})}u(k)\)
\(\Rightarrow n\sum_{d|n}\sum_{k|\frac{n}{d}}u(k)\sum_{i=1}^{\frac{n}{d}}i[k|i]\)
我们令 \(sum(x)=(1+2+...x)=(1+x)*x/2\),那么
\(\Rightarrow n\sum_{d|n}\sum_{k|\frac{n}{d}}k·u(k)sum(\left \lfloor \frac{n}{dk} \right \rfloor)\)
现在我们令 \(T=dk\),那么有:
\(n\sum_{T|n}sum(\left \lfloor \frac{n}{dk} \right \rfloor)\sum_{k|T}k·u(k)\)
可以看出我们可以在时间复杂度为 \(O(nlogn)\) 下预处理出 \(1-n\) 里面的所有值。
另外的推导:
\(\sum_{i=1}^{n}\frac{i·n}{gcd(i,n)}=\frac{1}{2}(\sum_{i=1}^{n-1}\frac{i·n}{gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i·n}{gcd(i,n)})+n\)
又由于 \(gcd(i,n)=gcd(n-i,n)\)
所以有 \(\frac{1}{2}(\sum_{i=1}^{n-1}\frac{i·n}{gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i·n}{gcd(n-i,n)})+n=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}+n=\frac{1}{2}\sum_{i=1}^{n}\frac{n^2}{gcd(i,n)}+\frac{n}{2}\) 。
然后有:\(\sum_{i=1}^{n}\frac{n^2}{gcd(i,n)}=n^{2}\sum_{d|n}\frac{1}{d}\sum_{i=1}^{n}[gcd(i,n)=d]=n^2\sum_{d|n}\frac{1}{d}\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]=n^2\sum_{d|n}\frac{1}{d}\varphi (\frac{n}{d})=\sum_{d|n}\frac{n^2\varphi (\frac{n}{d})}{d}\) 。
所以得到原式可以化简为:\(\frac{n}{2}(\sum_{d'|n}d'\varphi (d')+1)\)
现在我们可以看出我们可以在 \(O(nlog n)\) 的时间复杂度预处理出所有值。
不过 我们令 \(f(x)=\sum_{d|x}d\varphi(d)\),可以发现 \(f(x)\) 是一个积性函数,我们可以通过线性筛的形式 \(O(n)\) 预处理出所有值。
推导:\(f(p^k)=\sum_{w=0}^{k}p^w\varphi(p^w)=\sum_{w=0}^kp^{2w-1}(p-1)\),则 \(f(p^{k+1})=f(p^k)+p^{2k+1}(p-1)\) 。
如果 \(p|i\),则令 \(i=a·p^w \ (gcd(a,p)=1)\),得到 \(f(i*p)=f(a)f(p^{w+1})\)、\(f(i)=f(a)f(p^w)\) 。
则 \(f(i*p)-f(i)=f(a)*(f(p^{w+1})-f(p^w))=f(a)*p^{2w+1}(p-1)\),同理得到 \(f(i)-f(\frac{i}{p})=f(a)*(f(p^w)-f(p^{w-1}))=f(a)*p^{2w-1}(p-1)\) 。
因此得到 \(f(i*p)=f(i)+(f(i)-f(\frac{i}{p}))*p^2\) 。
时间复杂度为:\(O(n)\) 。
\((3)\):\(\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) \qquad (n,m \le 1e7)\)
\(\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i·j}{gcd(i,j)}=\sum_{d=1}^{min(n,m)}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{m}i·j[gcd(i,j)=d]=\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}i·j[gcd(i,j)=1]\)
我们先令 \(sum(x)=(1+2+...x)=(1+x)*x/2\)
我们令 \(f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}i·j\sum_{k|gcd(i,j)}u(k)=\sum_{k=1}^{min(n,m)}u(k)\sum_{i=1}^{n}i[k|i]\sum_{j=1}^{m}j[k|j]=\sum_{k=1}^{min(n,m)}u(k)k^2sum(\left \lfloor \frac{n}{k} \right \rfloor)sum(\left \lfloor \frac{m}{k} \right \rfloor)\)
则最后要求的答案为:\(\sum_{d=1}^{min(n,m)}f(\frac{n}{d},\frac{m}{d})\) ,得解。
\((4)\):约数个数和:\(\sum_{i=1}^{n}\sum_{j=1}^{m}d(i·j) \qquad (n,m,T \le 5e4)\) 。
其中 \(d(x)\) 表示 \(x\) 的约数个数,这里需要用到 \(d(x)\) 的一个性质。
标签:frac,gcd,积性,乌斯,sum,varphi,莫比,Rightarrow From: https://www.cnblogs.com/grapeking/p/18355569