参考链接数论符号以及函数模板:符号:\(连加:\) \(\sum_{i=1}^{n} i\)\(连乘:\) \(\prod_{i=1}^{n} i\)\(整除：（p为q的因子）p|q\)\(函数\)积性函数：\(积性函数指对于所有互质的整数a和b有性质f(a*b)=f(a)*f(b)的数论函数\) φ(n) －欧拉函数 μ(n) －莫比乌斯函数，关于非平方数的质因子数目 gcd(n,k) －最大公因子，当k固定的情况 d(n) －n的正因子数目 σ(n) －n的所有正因子之和 σk(n) － 因子函数，n的所有正因子的k次幂之和，当中k可为任何复数。 1(n) －不变的函数，定义为 1(n) = 1 （完全积性） Id(n) －单位函数，定义为 Id(n) = n（完全积性） Idk(n) －幂函数，对于任何复数、实数k，定义为Idk(n) = n^k （完全积性） ε(n) －定义为：若n = 1，ε(n)=1；若 n > 1，ε(n)=0。别称为“对于狄利克雷卷积的乘法单位”（完全积性） λ(n) －刘维尔函数，关于能整除n的质因子的数目 γ(n)，定义为γ(n)=(-1)^ω(n)，在此加性函数ω(n)是不同能整除n的质数的数目性质：\(由唯一分解定理：n = p_1^{a_1}*p_2^{a_2}...*p_i^{a_i}\)\((1)：f(n)=f\left(p_{1}^{a_{1}}\right) f\left(p_{2}^{a_{2}}\right) \ldots f\left(p_{n}^{a_{n}}\right)\)\((2)：f\left(p^{n}\right)=f^{n}(p)\)
常见的狄利克雷卷积：\(狄利克雷卷积运算：(f * g)(n)=\sum_{d | n} f(d) g\left(\frac{n}{d}\right)\)\(性质： 交换律：f∗g=g∗f 结合律：(f∗g)∗h=f∗(g∗h) 分配率：f∗(g+h)=f∗g+f∗h 单位元：f∗e=e∗f 若f,g 均为积性函数，则f∗g也为积性函数\)\(d(n)=\sum_{d | n} 1 \mathbb{即} d=1 * 1\)\(\sigma(n)=\sum_{d | n} d \mathbb{即} | \sigma=d * 1\)\(\varphi(n)=\sum_{d | n} \mu(d) \frac{n}{d} \mathbb{即} \varphi=\mu * I d\)\(\sum_{d | n} \varphi(d) \frac{n}{d} \mathbb等于p^{q-1}*(p+(p-1)*q) 其中设n=p^q:对于n=p_1^q_1*p_2^q_2...利用积性函数性质相乘即可\)
欧拉函数：\(欧拉函数通式：\) \(\varphi(n)=n * \prod_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right)\)\(性质：若n时质数p的k次幂则：\varphi(n)=p^{k}-p^{k-1}=(p-1) p^{k-1}，因为除了p的倍数外，其他数都跟n互质\)\(积性函数:\varphi(nm)=\varphi(n)\times\varphi(m)\)\(n为奇质数时:\varphi(2n)=\varphi(n)\)\(n为质数时:\varphi(n)=n-1\)\(与欧拉定理、费马小定理的关系\)\(对任何两个互质的正整数a, m(m>=2)有：a^{\varphi(p)} \equiv 1 \quad(\bmod p)\)
\(Möbius function(莫比乌斯函数)：\mu(d)=(-1)^{k}\)\(\mu(n)=\left\{\begin{array}{l}{1}，\space若n等于1 \\ {(-1)^{k}} ，若n无平方数因数且n=p1∗p2⋅⋅⋅pk\\ {0}，若n有平方因数\end{array}\right.\)
\(Dirichlet product(狄利克雷卷积) ，(f * g)(n)=\sum_{d | n} f(d) * g\left(\frac{n}{d}\right)\)
\(莫比乌斯反演:f(n)=\sum_{d | n} g(d)\)
\(杜教筛：已知数论函数f(n)，现在要求S(n)=\sum_{i=1}^{n} f(i)\)
转载于:https://www.cnblogs.com/Tianwell/p/11469522.html
相关资源：JAVA上百实例源码以及开源项目