几道数论题

论题"/>

几道数论题

鉴于数论题题面一般都挺短的，就不写题意了。

loj6052. 「雅礼集训 2017 Day11」DIV

其实令我最震惊的是这道题从头到尾可以和高斯整数一点关系都没有！（不过为了方便，还是引入一下比较好）
下面是推式子环节：
首先如果有等式
\[ (a + bi)(c + di) = k \]
根据复数的性质，很显然
\[ \frac{a}{b} = -\frac{c}{d} \]
设
\[ \frac{a}{b} = -\frac{c}{d} = \frac{p}{q} \]
且令\((p, q) = 1\)，有\(p | a, c\)， \(q | b, d\)

则
\[ \frac{a}{p}(p + qi) * \frac{c}{p}(p - qi) = k \]
即
\[ \frac {a}{p} \cdot \frac{c}{p}(p ^ 2 + q ^ 2) = k \]
而我们要求的是
\[ \sum_{k = 1} ^ n \sum_{a > 0} \sum_b [(a + bi) | k] * a \]
考虑一个复数\((p + qi)\)的贡献（其中\((p, q) = 1\)），因为\(q\)的正负性不关键，贡献是相同的，所以只要先考虑\(q > 0\)的情况即可（\(q = 0\)是另一类特殊情况）
\[ \begin{aligned} f(p, q) & = [(p, q) = 1] \sum_{k = 1} ^ n [(p ^ 2 + q ^ 2) | k] \sum_{x | \frac{k}{p ^ 2 + q ^ 2}} xp \\ & = [(p, q) = 1] * p\sum_{k = 1} ^ n [(p ^ 2 + q ^ 2) | k] \sigma_1(\frac{k}{p ^ 2 + q ^ 2}) \\ \end{aligned} \]
设\(r = p ^ 2 + q ^ 2\)，则
\[ \begin{aligned} f(p, q) & = [(p, q) = 1] * p \sum_{k = 1} ^ n [r | k] \sigma_1(\frac{k}{r}) \\ & = [(p, q) = 1] * p \sum_{k = 1} ^ {\lfloor \frac {n}{r} \rfloor} \sigma_1(k) \\ & = [(p, q) = 1]* p * D(\lfloor \frac {n}{r} \rfloor) \\ \end{aligned} \]
则
\[ \begin{aligned} \sum_{p, q} f(p, q) & = \sum_{r = 1} ^ {n} \sum_{(p, q) = 1 \\ p ^ 2 + q ^ 2 = r} p * D(\lfloor \frac{n}{r} \rfloor) \\ & = \sum_{r = 1} ^ {n} D(\lfloor \frac{n}{r} \rfloor) \sum_{(p, q) = 1 \\ p ^ 2 + q ^ 2 = r} p \\ \end{aligned} \]
其中，对于\(D(n)\)有
\[ D(n) = \sum_{i = 1} ^ n i \lfloor\frac{n}{i} \rfloor \]
考虑如果对\(\lfloor \frac{n}{r} \rfloor\)做除法分块，可以预处理前\(S\)个\(D(\frac{n}{r})\)，对于\(\frac{n}{r} > S\)的情况，直接再暴力做除法分块

但是要保证整体的复杂度还要要求
\[ \sum_{(p, q) = 1 \\ p ^ 2 + q ^ 2 = r} p \]
这个东西关于\(r\)的前缀和能快速求出

则设\(f(n) = \sum_\limits{(p, q) = 1, p ^ 2 + q ^ 2 \leq n} p\)，\(g(n) = \sum_\limits{p ^ 2 + q ^ 2 \leq n} p\)

则有
\[ g(n) = \sum_{d = 1} ^ n d * f(\lfloor \frac{n}{d ^ 2} \rfloor) \]
则
\[ f(n) = g(n) - \sum_{d = 2} ^ n d * f(\lfloor \frac {n}{d ^ 2} \rfloor) \]
其中\(g(n)\)能在\(\mathcal O(\sqrt n)\)的时间内得出

然后类似于杜教筛一样，\(f(n)\)也能在\(\mathcal O(n)\)的时间内算出（仍然不知道怎么证明）

如果我们提前将\(f(n)\)的前\(S\)项预处理一下，也能得到更好的复杂度

一般取\(S = n ^ {\frac {2}{3}}\)就可以了（复杂度不会证明啊）

loj6179. Pyh 的求和

求
\[ \sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij) \ (\bmod 998244353) \]
在\(n, m, T \leq 100000\)的情况下

看到这个式子，首先就回忆起那个式子
\[ \varphi(nm) = \frac{\varphi(n) * \varphi(m) * (n, m)}{\varphi((n, m))} \]
则
\[ \begin{aligned} \sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij) = & \sum_{i = 1} ^ n \sum_{j = 1} ^ m \frac{\varphi(i) * \varphi(j) * (i, j)}{\varphi(i, j)} \\ = & \sum_{d = 1} ^ n \frac{d}{\varphi(d)} \sum_{i = 1} ^ {\lfloor \frac{n}{d} \rfloor} \sum_{i = 1} ^ {\lfloor \frac{m}{d} \rfloor} [(i, j) = 1] \varphi(id) \varphi(jd) \\ = & \sum_{d = 1} ^ n \frac{d}{\varphi(d)} \sum_{g = 1} ^ {\lfloor \frac{n}{d} \rfloor} \mu(g) \sum_{i = 1} ^ {\lfloor \frac{n}{dg} \rfloor} \sum_{i = 1} ^ {\lfloor \frac{m}{dg} \rfloor} \varphi(idg) \varphi(jdg) \\ \end{aligned} \]
令\(t = dg\)，则
\[ \begin{aligned} \sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij) = & \sum_{t = 1} ^ n t \sum_{g | t} \frac{1}{g \varphi(\frac{t}{g})} \mu(g) \sum_{i = 1} ^ {\lfloor \frac{n}{t} \rfloor} \sum_{i = 1} ^ {\lfloor \frac{m}{t} \rfloor} \varphi(it) \varphi(jt) \\ = & \sum_{t = 1} ^ n f(t) \sum_{i = 1} ^ {\lfloor \frac{n}{t} \rfloor} \sum_{i = 1} ^ {\lfloor \frac{m}{t} \rfloor} \varphi(it) \varphi(jt) \\ = & \sum_{t = 1} ^ n f(t) \sum_{i = 1} ^ {\lfloor \frac{n}{t} \rfloor} \varphi(it) \sum_{i = 1} ^ {\lfloor \frac{m}{t} \rfloor} \varphi(jt) \\ = & \sum_{t = 1} ^ n f(t) * g(\lfloor \frac{n}{t} \rfloor, t) * g(\lfloor \frac{m}{t} \rfloor, t) \\ \end{aligned} \]
其中，\(f\)函数可以快速预处理出，\(g\)比较麻烦

把\(g\)拎出来考虑
\[ g(n, k) = \sum_{i = 1} ^ n \varphi(ik) \]
考虑到对于一个\(n\)来说，有用的\(k\)有\(\lfloor \frac{n}{k} \rfloor\)项，所以可以直接把所有要用的\(g(n, k)\)预处理出来，总共有\(O(n \ln n)\)项

但是这样还不够。因为考虑对于原式除法分块，要用的是\(g(\lfloor \frac{n}{t} \rfloor, t) * g(\lfloor \frac{m}{t} \rfloor, t)\)关于\(t\)的前缀和，但是这个东西是不能直接预处理的

考虑设定一个阈值\(S\)，预处理出\(n, m \leq S\)的\(f(k) * g(n, k) * g(m, k)\)的前缀和\(G(n, m, k)\)

然后在计算的时候，分类讨论

当\(t \leq S\)时，直接用预处理出来的计算

当\(t > S\)时，考虑到\(\lfloor \frac {n}{t} \rfloor, \lfloor \frac {m}{t} \rfloor\)比较小，可以直接用处理出来的\(g\)数组暴力计算即可

复杂度\(\mathcal O(n S ^ 2 + n \ln n + T (\frac{n}{S} + \sqrt n))\)

bzoj3512. DZY Loves Math IV

求
\[ \sum_{i = 1} ^ n \sum_{j = 1} ^ m \varphi(ij) \ (\bmod 1000000007) \]
由于\(n \leq 10 ^ 5\)比较小，\(m \leq 10 ^ 9\)比较大，所以考虑函数
\[ S(n, m) = \sum_{i = 1} ^ m {\varphi(ni)} \]
令\(q\)为\(n\)的每个素因子一次项的乘积，\(p = \frac{n}{q}\)，由于对于\(p | n\)，有\(\varphi(np) = \phi(n) * p\)，则
\[ \begin{aligned} S(n, m) = & \sum_{i = 1} ^ m \varphi(ni) \\ = & p \sum_{i = 1} ^ m \varphi(qi) \\ = & p \sum_{i = 1} ^ m \varphi(\frac{qi}{(q, i)}) * (q, i) \\ = & p \sum_{i = 1} ^ m \varphi(\frac{q}{(q, i)}) * \varphi(i) * (q, i) \\ = & p \sum_{i = 1} ^ m \varphi(\frac{q}{(q, i)}) * \varphi(i) \sum_{d | (i, q)} \varphi(d) \\ = & p \sum_{i = 1} ^ m \varphi(i) \sum_{d | (i, q)} \varphi(d) * \varphi(\frac{q}{(q, i)}) \\ = & p \sum_{i = 1} ^ m \varphi(i) \sum_{d | (i, q)} \varphi(\frac{qd}{(q, i)}) \\ = & p \sum_{i = 1} ^ m \varphi(i) \sum_{d | (i, q)} \varphi(\frac{q}{\frac{(q, i)}{d}}) \\ = & p \sum_{i = 1} ^ m \varphi(i) \sum_{d | (i, q)} \varphi(\frac{q}{d}) \\ = & p \sum_{i = 1} ^ m \varphi(i) \sum_{d | i, d | q} \varphi(\frac{q}{d}) \\ = & p \sum_{d | q} \varphi(\frac{q}{d}) \sum_{i = 1} ^ {\lfloor \frac{m}{d}\rfloor} \varphi(id) \\ = & p \sum_{d | q} \varphi(\frac{q}{d}) * S(d, \lfloor \frac{m}{d} \rfloor) \end{aligned} \]
因为数据范围较大，所以\(\varphi(x)\)要用杜教筛算，复杂度\(O(n ^ \frac{2}{3} \log n)\)

最后直接
\[ ans = \sum_{i = 1} ^ n S(i, m) \]
就好了

递归复杂度我也不知道怎么算

什么时候去学一学怎么算叭，算留一个坑

转载于:.html