数论学习

前言

近来发现自己的数论知识需要进行补充，感觉自己相对别人落下了好多，所以打算写一篇博客，跟进一下自己的知识储备

正文

1.数论函数

数论函数，指定义域为正整数、陪域为复数的函数
f:Z+→Cf:\mathbb{Z^+}\rightarrow\mathbb{C}f:Z+→C

• Tip:常数函数也是数论函数
  我们通常用一个数字代表常数函数，比如$1$代表$f(n)=1$,$x$代表$f(n)=x$

2.加性函数

对于一个函数$f$，如果对于$gcd(a,b)=1$满足$f(ab)=f(a)+f(b)$，就称其为加性函数

3.常见加性函数

• 质因子数
  ω(n)=∑p∣n1\omega(n)=\sum_{p|n}1ω(n)=p∣n∑​1
  $p$为质数
  $gcd(a,b)=1$说明$a,b$没有相同的质因子，所以这是加性函数
• 质因子之和
  a1(n)=∑p∣npa_1(n)=\sum_{p|n}pa1​(n)=p∣n∑​p
  $p$为质数
  证明同“相异质因子数”的证明

4.完全加性函数

对于一个函数$f$，如果$\forall a,b$满足$f(ab)=f(a)+f(b)$，就称其为完全加性函数

5.常见完全加性函数

• 可相同质因子数
  Ω(n)=∑p∣nt\Omega(n)=\sum_{p|n}tΩ(n)=p∣n∑​t
  $p$为质数，$t$为最大的整数满足pt∣np^t|npt∣n
  两数相乘，质因子数量可以直接合并
• 可相同质因子之和
  a0(n)=∑p∣np∗ta_0(n)=\sum_{p|n}p*ta0​(n)=p∣n∑​p∗t
  $p$为质数，$t$为最大的整数满足pt∣np^t|npt∣n
  证明同“可相同质因子数”的证明

6.积性函数

对于一个函数$f$，如果$f(1)=1$，且对于$gcd(a,b)=1$满足$f(ab)=f(a)\ast f(b)$，就称其为积性函数

• Tip：注意一定要满足$f(1)=1$，这个条件把函数$f(x)=0$这个函数排除了
  证明：
  $\because f(a)=f(a)\ast f(1)$
  $\therefore f(a)\ast (f(1)-1)=0$
  $\therefore f(1)=1或f(a)=0$

7.常见积性函数

• Euler’s totient function（欧拉函数）
  $\phi (n)$表示$[1,n]$中与$n$互质的数个数
  φ(n)=n∗∏i=1k(1−1pi)\varphi(n)=n*\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)φ(n)=n∗i=1∏k​(1−pi​1​)
  其中p1,p2……pkp_1, p_2……p_kp1​,p2​……pk​为$n$的所有质因数
  容易发现每个质因数$p$对$\phi (n)$的贡献都是独立的，设$t$为最大的整数满足pt∣np^t|npt∣n，其贡献的乘积为：(p−1)∗pt−1(p-1)*p^{t-1}(p−1)∗pt−1
  所以$\phi (n)$是积性函数
• Möbius function（莫比乌斯函数）
  μ(n)={1,若n=1(−1)k,若n无平方数因数且n=p1∗p2⋅⋅⋅pk0,若n有平方数因数\mu(n)=\begin{cases} 1,\ \ \ \ \ \ \ \ 若n=1 \\ (-1)^k,若n无平方数因数且n=p_1*p_2···p_k\\ 0,\ \ \ \ \ \ \ \ 若n有平方数因数 \end{cases}μ(n)=⎩⎪⎨⎪⎧​1,        若n=1(−1)k,若n无平方数因数且n=p1​∗p2​⋅⋅⋅pk​0,        若n有平方数因数​
  这是一个比较清楚的定义，容易发现每个质因数$p$对$\mu (n)$的贡献都是独立的，设$t$为最大的整数满足pt∣np^t|npt∣n，其贡献的乘积为：{−1,若t=10,若t>1\begin{cases}-1,若t=1\\ 0,\ \ \ 若t>1 \end{cases}{−1,若t=10,   若t>1​
  所以$\mu (n)$是积性函数
• divisor function（除数函数）
  σx(n)=∑d∣ndx\sigma_x(n)=\sum_{d|n}d^xσx​(n)=d∣n∑​dx
  这个积性函数的证明也非常简单，每加入一个质因数$p$对σx(n)\sigma_x(n)σx​(n)的贡献都是使值乘上一个定值，设$t$为最大的整数满足pt∣np^t|npt∣n，其贡献的乘积为∑i=0tpxi\sum_{i=0}^tp^{xi}i=0∑t​pxi
  所以除数函数还有一个式子是
  σx(n)=∏p∑pj∣npxj\sigma_x(n)=\prod_{p}\sum_{p^j|n}p^{xj}σx​(n)=p∏​pj∣n∑​pxj
  $p$为质数
  特殊的，σx(n)\sigma_x(n)σx​(n)有两个值得注意的情况
  σ0(n)\sigma_0(n)σ0​(n)代表$n$的因数数量，也写作$d(n)$
  σ1(n)\sigma_1(n)σ1​(n)代表$n$的因数之和，也写作$\sigma (n)$

8.完全积性函数

对于一个函数$f$，如果$f(1)=1$，$\forall a,b$满足$f(ab)=f(a)\ast f(b)$，就称其为完全积性函数

9.常见完全积性函数

• power function（幂函数）
  Idk(n)=nkId_k(n)=n^kIdk​(n)=nk
  证明很容易Idk(a)∗Idk(b)=ak∗bk=(a∗b)k=Idk(a∗b)Id_k(a)*Id_k(b)=a^k*b^k=(a*b)^k=Id_k(a*b)Idk​(a)∗Idk​(b)=ak∗bk=(a∗b)k=Idk​(a∗b)
  特殊的，Idk(n)Id_k(n)Idk​(n)有两个值得注意的情况
  Id0(n)=1Id_0(n)=1Id0​(n)=1，也写作$1(n)$或者是$I(n)$
  Id1(n)=nId_1(n)=nId1​(n)=n，也写作$Id(n)$
• Liouville function（刘维尔函数）
  λ(n)=(−1)Ω(n)\lambda(n)=(-1)^{\Omega(n)}λ(n)=(−1)Ω(n)
  $\Omega (n)$是完全加性函数，所以$\lambda (n)$是完全积性函数
• 单位函数
  ϵ(n)={1,n=10,n>1\epsilon(n)=\begin{cases}1,n=1\\0,n>1 \end{cases}ϵ(n)={1,n=10,n>1​
  特殊的，$ϵ(n)$有时也写作$e(n)$
  显然是完全积性函数

Dirichlet product（狄利克雷卷积）

两个数论函数$f,g$，他们的狄利克雷卷积为
(f∗g)(n)=∑d∣nf(d)∗g(nd)(f*g)(n)=\sum_{d|n}f(d)*g(\frac nd)(f∗g)(n)=d∣n∑​f(d)∗g(dn​)
相关性质：

• 交换律：$f\ast g=g\ast f$
  根据定义式可得
• 结合律：$(f\ast g)\ast h=f\ast (g\ast h)$
  展开
  ((f∗g)∗h)(n)=∑d∣n(f∗g)(d)∗h(nd)=∑d∣n(∑k∣df(k)∗g(dk))∗h(nd)=∑a∗b∗c=nf(a)∗g(b)∗h(c)\begin{aligned} ((f*g)*h)(n)&=\sum_{d|n}(f*g)(d)*h(\frac nd)\\ &=\sum_{d|n}(\sum_{k|d}f(k)*g(\frac dk))*h(\frac nd)\\ &=\sum_{a*b*c=n}f(a)*g(b)*h(c)\\ \end{aligned}((f∗g)∗h)(n)​=d∣n∑​(f∗g)(d)∗h(dn​)=d∣n∑​(k∣d∑​f(k)∗g(kd​))∗h(dn​)=a∗b∗c=n∑​f(a)∗g(b)∗h(c)​
  同理(f∗(g∗h))(n)=((g∗h)∗f)(n)=∑a∗b∗c=ng(a)∗h(b)∗f(c)(f ∗ (g ∗ h))(n)=((g*h)*f)(n)=\sum_{a*b*c=n}g(a)*h(b)*f(c)(f∗(g∗h))(n)=((g∗h)∗f)(n)=a∗b∗c=n∑​g(a)∗h(b)∗f(c)
  故$(f\ast g)\ast h=f\ast (g\ast h)$
• 分配律：$f\ast (g+h)=f\ast g+f\ast h$
  证明：
  ((g+h)∗f)(n)=∑d∣n(g(d)+h(d))∗f(nd)=∑d∣ng(d)∗f(nd)+∑d∣nh(d)∗f(nd)=(f∗g)(n)+(f∗h)(n)=(f∗g+f∗h)(n)\begin{aligned} ((g+h)*f)(n)&=\sum_{d|n}(g(d)+h(d))*f(\frac nd)\\ &=\sum_{d|n}g(d)*f(\frac nd)+\sum_{d|n}h(d)*f(\frac nd)\\ &= (f ∗ g)(n) + (f ∗ h)(n)\\ &= (f ∗ g+ f ∗ h)(n)\\ \end{aligned}((g+h)∗f)(n)​=d∣n∑​(g(d)+h(d))∗f(dn​)=d∣n∑​g(d)∗f(dn​)+d∣n∑​h(d)∗f(dn​)=(f∗g)(n)+(f∗h)(n)=(f∗g+f∗h)(n)​
• 单位元 $f\ast ϵ=f$
  显然
• 若$f,g$为积性函数，则$f\ast g$为积性函数，若$f,g$为完全积性函数，则$f\ast g$为完全积性函数
  证明：设$F=f\ast g$，要证的是$F(ij)=F(i)\ast F(j)$
  F(ij)=∑ab=ijf(a)∗g(b)F(ij)=\sum_{ab=ij}f(a)*g(b)F(ij)=ab=ij∑​f(a)∗g(b)
  F(i)∗F(j)=(∑a0b0=if(a0)∗g(b0))∗(∑a1b1=jf(a1)∗g(b1))=∑a0a1b0b1=ij(f(a0)∗f(a1))∗(g(b0)∗g(b1))=∑a0a1b0b1=ijf(a0a1)∗g(b0b1)=F(ij)\begin{aligned} F(i)*F(j)&=\left(\sum_{a_0b_0=i}f(a_0)*g(b_0)\right)*\left(\sum_{a_1b_1=j}f(a_1)*g(b_1)\right)\\ &=\sum_{a_0a_1b_0b_1=ij}(f(a_0)*f(a_1))*(g(b_0)*g(b_1))\\ &=\sum_{a_0a_1b_0b_1=ij}f(a_0a_1)*g(b_0b_1)\\ &=F(ij) \end{aligned}F(i)∗F(j)​=(a0​b0​=i∑​f(a0​)∗g(b0​))∗⎝⎛​a1​b1​=j∑​f(a1​)∗g(b1​)⎠⎞​=a0​a1​b0​b1​=ij∑​(f(a0​)∗f(a1​))∗(g(b0​)∗g(b1​))=a0​a1​b0​b1​=ij∑​f(a0​a1​)∗g(b0​b1​)=F(ij)​

常见的狄利克雷卷积式子

• $d=1\ast 1$
  d(n)=∑d∣n1d(n)=\sum_{d|n}1d(n)=d∣n∑​1
• $\sigma =Id\ast 1$
  σ(n)=∑d∣nd\sigma(n)=\sum_{d|n}dσ(n)=d∣n∑​d
• $ϵ=\mu \ast 1$
  ϵ(n)=∑d∣nμ(d)\epsilon(n)=\sum_{d|n}\mu(d)ϵ(n)=d∣n∑​μ(d)
  证明：
  设$n$有$k$个相异质因子
  若$k=0$，那么结果为$1$
  否则∑d∣nμ(d)=∑i=0k(−1)i(ki)=(1−1)k=0\begin{aligned} \sum_{d|n}\mu(d)&=\sum_{i=0}^k(-1)^i\dbinom{k}{i}\\ &=(1-1)^k\\ &=0 \end{aligned}d∣n∑​μ(d)​=i=0∑k​(−1)i(ik​)=(1−1)k=0​
• $\phi =\mu \ast Id$
  φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d|n}\mu(d)\frac ndφ(n)=d∣n∑​μ(d)dn​
  证明：
  首先证明：$\phi \ast 1=Id$
  即
  ∑d∣nφ(d)=n\sum_{d|n}\varphi(d)=nd∣n∑​φ(d)=n
  yangxin2003的形象证明
  给定一个$n$，枚举1n,2n⋅⋅⋅nn\frac 1n,\frac 2n···\frac nnn1​,n2​⋅⋅⋅nn​，并将每个约分
  考虑枚举约分后的分母（即枚举$d$），$\phi (d)$即为$d$为分母时的最简分数数量，对应上面的$n$个数
  证完之后然后莫比乌斯反演（下面会提到）即可

Möbius inversion formula（莫比乌斯反演）

$$f=g\ast 1\iff g=u\ast f$$
另一种表示方式：
如果多项式$f,g$满足f(n)=∑d∣ng(d)f(n)=\sum_{d|n}g(d)f(n)=d∣n∑​g(d)
那么也一定满足g(n)=∑d∣nμ(d)f(nd)g(n)=\sum_{d|n}\mu(d)f(\frac nd)g(n)=d∣n∑​μ(d)f(dn​)
反之也成立
证明：
设$$f=g\ast 1$$
两边卷上$\mu$
$$\mu \ast f=\mu \ast g\ast 1$$
整理
$$\mu \ast f=ϵ\ast g=g$$
即$$g=\mu \ast f$$
反过来同理

欧拉筛

每个数都只会被其最小的质因数筛到
复杂度$\Theta (n)$，适合筛各种积性函数

inline void getlist(const int listsize)
{memset(isprime,1,sizeof(isprime));isprime[1]=0;for(rg int i=2;i<=listsize;i++){if(isprime[i]==1)prime[++primesize]=i;for(int j=1;j<=primesize&&(LL)i*(LL)prime[j]<=(LL)listsize;j++){isprime[i*prime[j]]=0;if(i%prime[j]==0)break;}}
}

• Tip：对于欧拉筛有一个小技巧，可以开桶记录每个数的最小质因子，那么就可以做到$\Theta (n)$预处理，单次$\Theta (logn)$的质因数分解复杂度了
• Tip：单次的分解质因数复杂度是Θ(n)\Theta(\sqrt n)Θ(n​)的，枚举小于n\sqrt nn​的数，如果整除就除掉，如果最后剩下的值不为1，那么剩下的这个值也是一个质因数，次数为1

杜教筛

现在有个数论函数$f(n)$，现在要求S(n)=∑i=1nf(i)S(n)=\sum_{i=1}^nf(i)S(n)=∑i=1n​f(i)
杜教筛的核心思想是：找到一个数论函数$g(n)$
因为显然满足∑i=1n∑d∣if(d)g(id)=∑i=1ng(i)S(⌊ni⌋)\sum_{i=1}^n\sum_{d|i}f(d)g(\frac id)=\sum_{i=1}^ng(i)S(\left\lfloor \frac ni\right\rfloor)i=1∑n​d∣i∑​f(d)g(di​)=i=1∑n​g(i)S(⌊in​⌋)
所以就有$S(n)$的递推式：
g(1)S(n)=∑i=1n(f∗g)(i)−∑i=2ng(i)S(⌊ni⌋)g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\left\lfloor \frac ni\right\rfloor)g(1)S(n)=i=1∑n​(f∗g)(i)−i=2∑n​g(i)S(⌊in​⌋)

• Tip：能用杜教筛的前提是找到了合适的$g(n)$，杜教筛能够筛某几种特定的积性函数，在下面会分别列举

常见杜教筛板子

• 求$\phi (n)的前缀和S(n)$
  我们已经知道$$\phi \ast 1=Id$$
  那么在$f=\phi$的条件下，$g=1$无疑是最佳选择，
  那么，上面的递推式就变成了
  S(n)=∑i=1ni−∑i=2nS(⌊ni⌋)S(n)=\sum_{i=1}^ni-\sum_{i=2}^nS(\left\lfloor \frac ni\right\rfloor)S(n)=i=1∑n​i−i=2∑n​S(⌊in​⌋)
  首先证明这个递推式里的元素数量是Θ(n)\Theta(\sqrt n)Θ(n​)的
  解释：
  ∵⌊⌊xa⌋b⌋=⌊xab⌋∴所有被访问的元素为⌊ni⌋元素数是Θ(n)的设m=n这些元素是1,2⋅⋅⋅,m−1,m,⌊nm⌋,⌊nm−1⌋⋅⋅⋅,⌊n2⌋,⌊n1⌋\because\left\lfloor\frac {\left\lfloor\frac xa\right\rfloor}b \right\rfloor=\left\lfloor\frac x{ab} \right\rfloor\\ \therefore所有被访问的元素为\left\lfloor\frac ni \right\rfloor\\ 元素数是\Theta(\sqrt n)的\\ 设m=\sqrt n\\ 这些元素是1,2···,m-1,m,\left\lfloor\frac nm\right\rfloor,\left\lfloor\frac n{m-1}\right\rfloor···,\left\lfloor\frac n2\right\rfloor,\left\lfloor\frac n1\right\rfloor∵⌊b⌊ax​⌋​⌋=⌊abx​⌋∴所有被访问的元素为⌊in​⌋元素数是Θ(n​)的设m=n​这些元素是1,2⋅⋅⋅,m−1,m,⌊mn​⌋,⌊m−1n​⌋⋅⋅⋅,⌊2n​⌋,⌊1n​⌋
  然后考虑算法复杂度
  对于上面那个式子的第一项显然是(1+n)∗n2\frac {(1+n)*n}22(1+n)∗n​，计算是$\Theta (1)的$
  对于第二项，刚才已经证明⌊ni⌋\left\lfloor\frac ni \right\rfloor⌊in​⌋的取值只有Θ(n)\Theta(\sqrt n)Θ(n​)个，那么我们只要枚举每个取值，计算其贡献次数即可
  复杂度的式子是
  ∑i=1⌊n⌋Θ(i)+∑i=1⌊n⌋Θ(ni)\sum_{i=1}^{\left\lfloor \sqrt n\right\rfloor}\Theta(\sqrt i)+\sum_{i=1}^{\left\lfloor \sqrt n\right\rfloor}\Theta(\sqrt{\frac ni})i=1∑⌊n​⌋​Θ(i​)+i=1∑⌊n​⌋​Θ(in​​)
  这个式子的结果是Θ(n34)\Theta(n^{\frac 34})Θ(n43​)
  由于前面的n\sqrt nn​个值可以用线性筛跑出来，所以复杂度为
  n+∑i=1⌊n⌋Θ(ni)\sqrt n+\sum_{i=1}^{\left\lfloor \sqrt n\right\rfloor}\Theta(\sqrt{\frac ni})n​+i=1∑⌊n​⌋​Θ(in​​)
  瓶颈在后一半，所以可以通过调整块大小来优化复杂度
  设我们筛前$k$个，那么前面一项的复杂度为$\Theta (k)$，后面一项的复杂度为Θ(nk)\Theta(\frac n{\sqrt k})Θ(k​n​)（这个的复杂度证明是根据微积分可得∑i=1nΘ(1i)=Θ(n)\sum_{i=1}^n\Theta(\frac 1{\sqrt i})=\Theta(\sqrt n)∑i=1n​Θ(i​1​)=Θ(n​)，然后带入得Θ(n)∗Θ(nk)=Θ(nk)\Theta(\sqrt n)*\Theta(\sqrt {\frac nk})=\Theta(\frac n{\sqrt k})Θ(n​)∗Θ(kn​​)=Θ(k​n​)），总复杂度最优时
  k=nk,k32=n,k=n23k=\frac n{\sqrt k},k^{\frac 32}=n,k=n^{\frac 23}k=k​n​,k23​=n,k=n32​
  最优复杂度为Θ(n23)\Theta(n^{\frac 23})Θ(n32​)
  代码

#include
#include
#include
#include
#include
namespace fast_IO
{const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
//#define getchar() getchar_()
//#define putchar(x) putchar_((x))
//#include
#define rg register
typedef long long LL;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
//template  inline void swap(T*a,T*b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int MAX=2000000;
bool isprime[MAX+1];
int n,prime[MAX+1],primesize;LL phi[MAX+1],phi1[MAX+1];
inline void getlist(const LL listsize)
{memset(isprime,1,sizeof(isprime));isprime[1]=0,phi[1]=1;;for(rg int i=2;i<=listsize;i++){if(isprime[i])prime[++primesize]=i,phi[i]=i-1;for(rg int j=1;j<=primesize&&(LL)i*prime[j]<=listsize;j++){isprime[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}phi[i*prime[j]]=phi[i]*(prime[j]-1);}}
}
inline LL Val(const int x)
{if(x<=MAX)return phi[x];return phi1[n/x];
}
int main()
{getlist(MAX);for(rg int i=1;i<=MAX;i++)phi[i]+=phi[i-1];read(n);for(rg int i=min((int)sqrt(n),n/(MAX+1));i>=1;i--){const int u=n/i;LL res=(LL)u*(u+1)/2;int limit=sqrt(u);for(rg int j=1;j<=limit;j++)res-=Val(u/j);limit++;for(rg int j=1;limit*j<=u;j++)res-=phi[j]*((u/j)-(u/(j+1)));phi1[i]=res;}print(Val(n));return flush(),0;
}

• 求$\mu (n)$的前缀和$S(n)$
  同样的，我们可以找到一个$g(n)$，没错又是$1$，因为$\mu \ast 1=ϵ$
  所以带入式子S(n)=1−∑i=2nS(⌊ni⌋)S(n)=1-\sum_{i=2}^nS(\left\lfloor \frac ni\right\rfloor)S(n)=1−i=2∑n​S(⌊in​⌋)
  哇，这不是东西更少了吗，和上面一样的思路，复杂度Θ(n23)\Theta(n^{\frac 23})Θ(n32​)
  代码

#include
#include
#include
#include
#include
namespace fast_IO
{const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
//#define getchar() getchar_()
//#define putchar(x) putchar_((x))
//#include
#define rg register
typedef long long LL;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;}
//template  inline void swap(T*a,T*b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int MAX=2000000;
bool isprime[MAX+1];
int T,n;
int prime[MAX+1],primesize;LL mu[MAX+1],mu1[MAX+1];
inline void getlist(const LL listsize)
{memset(isprime,1,sizeof(isprime));isprime[1]=0,mu[1]=1;for(rg int i=2;i<=listsize;i++){if(isprime[i])prime[++primesize]=i,mu[i]=-1;for(rg int j=1;j<=primesize&&(LL)i*prime[j]<=listsize;j++){isprime[i*prime[j]]=0;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}mu[i*prime[j]]=-mu[i];}}
}
inline LL Val(const int x)
{if(x<=MAX)return mu[x];return mu1[n/x];
}
int main()
{getlist(MAX);for(rg int i=1;i<=MAX;i++)mu[i]+=mu[i-1];read(n);for(rg int i=min((int)sqrt(n),n/(MAX+1));i>=1;i--){const int u=n/i;LL res=1;int limit=sqrt(u);for(rg int j=1;j<=limit;j++)res-=Val(u/j);limit++;for(rg int j=1;limit*j<=u;j++)res-=mu[j]*((u/j)-(u/(j+1)));mu1[i]=res;}print(Val(n));return flush(),0;
}

其实代码差不太多

Min25筛

内容太多辣，可以看我另一篇博客Min_25筛学习Tip+链接
也是做积性函数前缀和的，并且能使得很多题目得到简化

我是分割线，目前要写的内容就这么多了，想到再更

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！