被迫营业。应用范围：求\(\sum_{i=1}^nf(i)\)，其中\(f(i)\)是积性函数。需要满足\(f(i)\)在\(i\)是质数时的取值是多项式。时间复杂度：\(\Theta(n^{1-\epsilon})\)/\(\Theta(\frac{n^{\frac{3}{4}}}{\logn})\)。主要想法是将\(f(i)\)分成三个部分后求和：\(i\)是质数，\(

积性函数一般我们只需要考虑定义域在\(\mathbb{Z}\)就够了，什么实数，复数都不用管。如果函数\(f(x)\)满足对于任意的\(a,b\)且\(\gcd(a,b)=1\)，都有\(f(ab)=f(a)f(b)\)。欧拉函数\(\varphi(i)\)\(\varphi(n)\)定义为大于等于\(1\)且小于\(n\)且与它互质的数的个数

一、莫比乌斯1、莫比乌斯函数：\(u(n)=\left\{\begin{array}{l}1\qquad\qquadn=1\\0\qquad\qquadn含有平方因子\\(-1)^{k}\qquadn里面所包含质因子数目\end{array}\right.\)令\(\varepsilon(n)=\sum_{d|n}^{n}u(d)=[n=1]\)，那么我们有\(\varepsilon=u\*\1\)

积性函数和狄利克雷卷积学习笔记积性函数定义若函数\(f(x)\)满足\(f(ab)=f(a)f(b)\)，其中\(a,b\)互质，我们称这个函数是积性函数。若\(a,b\)不互质则是完全积性函数。常见积性函数狄利克雷卷积定义也叫狄利克雷乘积。形如下式：\[h(n)=\sum_{ab=n,a>0,b>0}f(a)g(b)\]

数论函数定义：定义域为正整数的函数。积性函数：若数论函数\(f\)满足\(\gcd(x,y)=1\)则\(f(xy)=f(x)f(y)\)，\(f\)就是一个积性函数。完全积性函数：若\(f(xy)=f(x)f(y)\)，则\(f\)为一个完全积性函数。若积性函数\(f(1)\ne0\)，则\(f(1)=1\)，容易由定义推得。

数论函数基础数论函数是数论中相当重要的一环，我们先来将*一些基本的函数——\(\color{black}\textsf{H}\color{red}\textsf{\_W\_Y}\)*:同“讲”，讲述全文绝大多数内容是对[0]中讲述的粗略抄写和胡乱加工关于加性函数和积性函数的部分，参考[3]1

前置知识：积性函数。定义：一个函数\(f\)，若\(\forall\gcd(a,b)=1\)，都有\(f(a)\timesf(b)=f(a\timesb)\)，则它是积性函数。一个函数\(f\)，若\(\forall(a,b)\)，都有\(f(a)\timesf(b)=f(a\timesb)\)，则它是完全积性函数。正题狄利克雷卷积先放一张图方便下文理解(copyz

0.更新upd2023.5.21更新了关于powerfulnumber数量的证明upd2023.5.25更新了关于杜教筛的时间复杂度证明正文1.筛质数筛法其实就是判断质数的一个算法，但是是解决\([1,n]\)这一段区间的算法筛质数是最简单的一个用法1.1暴力最简单的方式就是对于每一个数去判断

一般函数\(\times\)一般函数\(O(n\logn)\)暴力即可，\(O(n\logn)\)一般函数\(\times\)积性函数\(O(n\log\logn)\)对每一个指数跑类似FWT的东西，\(O(n\log\logn)\)积性函数\(\times\)积性函数\(O(n)\)如果我们能把每一个质数\(p^a\)的答案得到，我们就能欧拉筛

积性函数1.利用欧拉筛求f(1),……,f(n)//欧拉筛求f(1),……,f(n)voideuler{ f[1]=1; for(inti=2;i<=n;i++){ if(!st[i])p[++tot]=i,f[i]=calc_f(i,1); for(intj=1;j<=tot&&i*p[j]<=n;j++){ st[i*p[j]]=true; if(i%p[j]==0){ cnt[i*p[j]]=cnt[i]+1;//cnt

数论函数积性函数积性函数：对于任何互质的整数有\(f(a\cdotb)=f(a)\cdotf(b)\)的数论函数。完全积性函数：对于任何整数有\(f(a\cdotb)=f(a)\cdotf(b)\)的数论函数。常见积性函数：欧拉函数\(\varphi\)，莫比乌斯函数\(\mu\)，因数个数函数\(\tau\)，因数和函数\(\si

积性函数：若函数\(f(x)\)满足：\(f(1)=1\)且\(∀x,y∈N_+,\gcd(x,y)=1\)都有\(f(xy)=f(x)f(y)\)，则称它为积性函数。若函数\(f(x)\)满足：\(f(1)=1\)且\(∀x,y∈N_+\)都有\(f(xy)=f(x)f(y)\)，则称它为完全积性函数。性质：若\(f(x),g(x)\)均为积性函数，那么则以下函数也为

听zak讲的，感觉很厉害。给定一个积性函数\(S\)，可以快速计算\(S(p^k)\)，求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^mS(ij)\)。把\(n,m\)当作同阶。我们考虑枚举\(i,j\)的\(\gcd\)。\(\sum\limits_{g=1}^{\min(n,m)}\sum\limits_{i=1}^{n/g}\sum\limits_{j=1}^{m/g}S

积性函数【定义】若对于一个数论函数\(f\)，有：对\((a,b)=1\)，有\(f(a\timesb)=f(a)\timesf(b)\)，称\(f\)是一个积性函数。特别地，若对于任意数\(a,b\)，有\(f(a\timesb)=f(a)\timesf(b)\)，称\(f\)是一个完全积性函数。积性函数举例：欧拉函数，因数个数，因数和……完

前置：积性函数与狄利克雷卷积和整除分块两个基础积性函数：\(\varepsilon(n)=[n=1]\)，\(1(n)=1\)。性质：\(\varepsilon*f=f\)，\(f\)是任意函数。结论：\(f(n)\)是积性函数\(\iffg(n)=\displaystyle\sum_{d|n}f(d)\)是积性。证明：$\Rightarrow$方向：\(g=f*1\)，狄利克雷卷积的性

积性函数定义积性函数：\(f(x)\)满足\(\forall\gcd(a,b)=1,f(ab)=f(a)f(b)\)若没有\(\gcd(a,b)=1\)的性质，则为完全积性函数。性质性质1:\(f(x),g(x)\)是积性函数\(\implies\)\(f\timesg\)是积性函数，\(f\divg\)是积性函数证明略。性质2：狄利克雷（Dirichlet）卷积\(

积性函数定义1积性函数，若称数论函数\(f(n)\)为积性函数，则其需要满足以下性质：\[\foralln\perpm,f(nm)=f(n)\timesf(m)\]定义2完全积性函数，若称数论函数\(f(n)\)为完全积性函数，则其需要满足以下性质：\[\foralln,m,f(nm)=f(n)\timesf(m)\]下面我们说几个积性函数

一、引言欧式筛/欧拉筛法/线性筛法（EulerSieve）是一种能够在\(O(n)\)时间复杂度内，处理\([1,n]\)内质数的方法。其相比埃氏筛/埃拉托斯特尼筛法（EratosthenesSieve）的\(O(n\log\logn)\)时间复杂度，主要的优化在于欧式筛保证了所有正整数\(n\)均只被其最小质因数\({minp}_n

前言/声明首先，本人的数论水平极低，目前莫反只是刚刚入门的水平，此博客的主要作用是用于记录本人的学习过程，真的想要深入了解莫反的话这边推荐cmd大佬的博客（点这里），应该对你有更大帮助。建议学习的时候能多理解些就多去理解，少硬记些结论，这样更不容易忘记。前置知识：最基础的数论。

BaseSievebaseDirichletConvolutionSqrtDecomposition会挖坑，好让复习的时候长脑子。以下所有\(p\)都是质数，即\(p\in\mathbb{P}\)，同时默认均为正整数。Base唯一分解定理（算术基本定理）：\[\begin{align} \foralln>1,n=\prod\limits_{i=1}^kp_i^{t_i}\end{align}\]

定义记欧拉函数\(\varphi(n)\)表示\(1\simn\)与\(n\)互质的整数的个数。性质若\(p\)为质数，则\(\varphi(p^k)=(p-1)\cdot\varphi(p^{k-1})\)。\(\varphi\)是积性函数。（积性函数\(f\)：若\(a,b\)互质，则满足\(f(ab)=f(a)\cdotf(b)\)）若\(n=\prod_{i=1}^mp_i^{\al

1.图上异或题从雷暴那里看到的估计是nfls模拟赛题。给定一张带边权图，询问从1开始出发的路径，边权异或和一共有多少不同的权值。还有若干次删边操作（永久的），删一次问一次。P4151【[WC2011]最大XOR和路径】的结论，取出任意生成树\(T\)，假设所有从\(1\)出发又回到\(1\)的路

因为模拟赛太频繁已经很久没有写闲话了今天搜到的一道IMOShortlist题，挺水的，但是还挺好玩先反演一波：\[a_n=\sum_{d|n}2^d\mu(\fracnd)\]然后因为\(\mu\)和\(2^n\)都是积性的，所以\(a_n\)是积性的，只需要考虑素数幂处的取值即可\[a_{p^k}=\sum_{i=0}^{k}2^{p^i}\mu(

1.基础数论函数定义:数论函数,就是值域为整数(陪域为复数)的函数狄利克雷卷积两个数论函数的狄利克雷卷积是一个新的函数比如\(f(n)\),\(g(n)\)它们的卷积就是\(f*g\)怎么卷呢？定义:\(\large{(f*g)(n)=\sum\limits_{d|n}f(n)g(n/d)}\)举个例子：\((f*g)(12)=f(1)*g

\(Update\:\:on\:\:2023.8.3\)：增加了积性函数的内容，修改了内容排版Part1：欧拉函数及其性质定义：欧拉函数\(φ(n)\)表示小于等于\(n\)，且与\(n\)互质的正整数的个数。公式：若在算数基本定理中，\(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)（\(p\)为质数），则由容斥原理：\[φ(n)=n*\d