Memphis's Blog

其实我填坑的初衷不是为了填坑而是为了实验一下tex

此篇目绝对不会涉及高难度的东西，想看高难度的可以出门右转右下的友情list链接

我们从最基础的讲起，其实是我的复(zi)习(xue),请尽情的享受我的口胡吧

后注：本篇全篇口胡，很多地方是错的，仅供参考

---

辗转相除法/欧几里德算法

我们要求[tex]gcd(a,b)[/tex]

设[tex]d=gcd(a,b)[/tex]

[tex]d|a, d|b[/tex]

设[tex]y=a-bx[/tex]

[tex] d|y[/tex]

[tex]d|a~mod~b[/tex]

[tex]gcd(a,b)=gcd(b,a~mod~b)~~~~(1)[/tex]

递归求解

复杂度证明应该很显然吧w

---

扩展欧几里德算法

我们要求[tex]ax+by=gcd(a,b)[/tex]

[tex]bx+(a~mod~b)y=gcd(b,a~mod~b)[/tex]

由定理[tex](1)~~gcd(a,b)=gcd(b,a~mod~b)[/tex]

[tex]bx'+(a~mod~b)y'=ax+by[/tex]

[tex] bx'+(a-\lfloor\frac{a}{b}\rfloor b)y'=ax+by[/tex]

[tex]b(x'-\lfloor\frac{a}{b}\rfloor y')+ay'=by+ax[/tex]

[tex]y=x'-\lfloor\frac{a}{b}\rfloor y',x=y'[/tex]

递归求解

---

法莱序列

我们要求[tex] \frac{A}{B}<\frac{x}{y}<\frac{C}{D}[/tex]

[tex] \frac{B}{A}>\frac{y}{x}>\frac{D}{C}[/tex]

[tex] \frac{B-\lfloor\frac{B}{A}\rfloor A}{A}>\frac{y-\lfloor\frac{B}{A}\rfloor x}{x}>\frac{D-\lfloor\frac{B}{A}\rfloor C}{C}[/tex]

设[tex]A'=B-\lfloor\frac{B}{A}\rfloor A,B'=A,C'=D-\lfloor\frac{B}{A}\rfloor C,D'=C[/tex]

设[tex]x'=y-\lfloor\frac{B}{A}\rfloor x,y'=x[/tex]

[tex]x=y',y=x'+\lfloor\frac{B}{A}\rfloor x~~~~(2)[/tex]

递归求解[tex] \frac{A'}{B'}<\frac{x'}{y'}<\frac{C'}{D'}[/tex]

终止条件[tex] \frac{C'}{D'}>1[/tex]

[tex]return~~~x'=1,y'=1[/tex]

由[tex](2)[/tex]代入回溯

算法和复杂度和上面两个算法类似

---

线性筛法

用最小最大表示法可以唯一确定表示质因数分解[tex]~x=\prod_{i}{p_i^{q_i}}~~~~~~~(3)[/tex]

假设确定了一个数[tex]~x~[/tex]的最小质因子[tex]~p_x~[/tex]和小于[tex]~p_x~[/tex]的素数表[tex]~Prime_{1\sim len}[/tex]，

我们就可以确定由[tex]~x~[/tex]拓展出去得到其他数的最小质因子，

这些数是[tex]~Prime_i*x~[1<=i<=len,Prime_i<=p_x]~[/tex]

由[tex](3)[/tex]可以知道每个数只被筛到了一次，所以是线性的

另[tex]~p_x=0~[/tex]的[tex]x[/tex]是素数，赋值[tex]p_x[/tex]为[tex]x[tex]

线性筛法还可以用来求积性函数

---

离散对数/大步小步（BSGS,Baby Step Giant Step）

我们要求[tex]A^a\equiv B(~mod~C)[~C~is~a~prime~][/tex]

[tex]A^{xS+y}\equiv B(~mod~C)[/tex]

[tex] A^{xS}\equiv \frac{B}{A^y}(~mod~C)[/tex]

将同余符号右边的式子[tex]O(S)[/tex]放入hash表中

然后用左边的式子[tex]O(\frac{C}{S})[/tex]一一验证是否存在同余关系

复杂度最优时[tex]S=\sqrt{C}[/tex]

---

拓展离散对数

我们要求[tex]A^a\equiv B(~mod~C)[/tex]

设[tex]D=A^a,~D\equiv B(~mod~C)[/tex]

[tex]D=kC+B[/tex]

[tex]\frac{D}{t}=k\frac{C}{t}+\frac{B}{t}[/tex]

[tex]\frac{D}{t}\equiv \frac{B}{t}(~mod~\frac{C}{t})[/tex]

[tex]t=gcd(A,C)

[tex]if~t\nmid B,~No~Solution[/tex]

迭代直到[tex]gcd(C_s,A)=1[/tex]

[tex]E=gcd(A,C)gcd(A,C_1)...gcd(A,C_{s-1})[/tex]

[tex] A^{a-s}\frac{A^s}{E}\equiv \frac{B}{E}(~mod~\frac{C}{E})[/tex]

注意此处左右的分母相同，其实作者不清楚是否可以直接约掉orz

[tex]B'=\frac{B}{E}[/tex]

[tex]A^{a-s}\equiv \frac{B'E}{A^s}(~mod~\frac{C}{E})[/tex]

由非拓展离散对数的方法求出[tex]~F=a-s[/tex]

[tex]F+s~[/tex]是一个可行解

最后还需要枚举[tex]A^{1\sim s}[/tex]判断一下是否有可行解处于[tex]1\sim s[/tex]中

---

莫比乌斯反演

我们要求[tex]\sum_{i=1}^{n}{\sum_{j=1}^{m}{f(gcd(i,j))}}[/tex]

其中[tex]f(x)[/tex]是一个自定义的函数

[tex]x=\prod_{i=1}^{k_x}{p_i^{q_i}}[/tex],我们定义这样两个函数：

[tex]e(x)=\begin{cases}0~~~~~~~~~~x>1\\1~~~~~~~~~~x=1}\end{cases}~~~~~~~~~~~~~~~~~~~(1)[/tex]

[tex]\mu(x)=\begin{cases}1~~~~~~~~~~x=1\\(-1)^{k_x}~~~\forall~q_i,~q_i<2\\0~~~~~~~~~~\exists~q_i,~q_i>=2}\end{cases}~~~~~~~~(2)[/tex]

有定理：[tex]e(x)=\sum_{d|x}{\mu(d)}[/tex]

证明如下：

[tex]\sum_{d|x}{\mu(d)}=\sum_{i=0}^{k_x}{\binom{k_x}{i}(-1)^i[/tex]

[tex]\sum_{d|x}{\mu(d)}=(1-1)^{k_x}[/tex]

当[tex]k_x=0[/tex]时[tex]\sum_{d|x}{\mu(d)}=1[/tex]

当[tex]k_x>0[/tex]时[tex]\sum_{d|x}{\mu(d)}=0[/tex]

得证：[tex]e(x)=\sum_{d|x}{\mu(d)}[/tex]

回过头来看我们最初的问题：

[tex]\sum_{i=1}^{n}{\sum_{j=1}^{m}{f(gcd(i,j))}}[/tex]

枚举[tex]d_1=gcd[/tex]

[tex]=\sum_{d_1=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{d_1} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{d_1} \rfloor}{f(d_1)e(gcd(i,j))}}}[/tex]

[tex]=\sum_{d_1=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{d_1} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{d_1} \rfloor}{f(d_1)\sum_{d_2|gcd(i,j)}{\mu(d_2)}}}}[/tex]

[tex]=\sum_{d_1=1}^{min(n,m)}{\sum_{d_2=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{d_1 d_2} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{d_1 d_2} \rfloor}{f(d_1)\mu(d_2)}[/tex]

枚举[tex]c=d_1 d_2[/tex]

[tex]=\sum_{c=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{c} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{c} \rfloor}{\sum_{d|c}{f(d)\mu(\frac{c}{d})}}}}[/tex]

[tex]=\sum_{c=1}^{min(n,m)}{\sum_{d|c}{f(d)\mu(\frac{c}{d})}\lfloor \frac{n}{c} \rfloor\lfloor \frac{m}{c} \rfloor}[/tex]

[tex]g(c)=\sum_{d|c}{f(d)\mu(\frac{c}{d})}[/tex]

[tex]=\sum_{c=1}^{min(n,m)}{g(c)\lfloor \frac{n}{c} \rfloor\lfloor \frac{m}{c} \rfloor}~~~~~~~~ (1) [/tex]

[tex]\mu(x)[/tex]是积性函数，若[tex]f(x)[/tex]同样是积性函数那么[tex]g(x)[/tex]也是积性函数，这是一个狄利克雷卷积。

证明我还没想过QAQ

如果不是积性函数[tex]g(x)[/tex]可以用枚举约数的筛法[tex]O(nln(n))[/tex]求得

如果是积性函数可以用上面说过的欧拉线性筛法[tex]O(n)[/tex]求得

求[tex]g(x)[/tex]的最优复杂度就是这样了。

单次回答询问也可以用[tex](1)~O(n)[/tex]求得。

但还有对于询问[tex]\sqrt{n}[/tex]的做法。

 

Loading...