UOJ Logo zhengjiarui的博客

博客

原根&杜教筛 上课笔记

2019-04-13 11:03:05 By zhengjiarui

原根

$$ a^{1, 2, \cdots ,p-1} \\ Ord_m(i) 是使 a^d \equiv 1 \ (mod\ m) \\ 最小的d \ gcd(a,m)=1 \\ Ord_m(a) \leq \varphi ( m ) \\ Ord_m(a) | \varphi(m) \\ a^n \equiv 1\ (mod \ m) \\ d|n \\ Ord_m(a) = \varphi(m)\ a是m的原根 \\ 2,4,P^n,2 \cdot P^n (P是积质数) \\ m^{\frac 1 4} \\ g是原根,g^d是原根 \\ gcd(d,\varphi(m)) =1 \\ \varphi(\varphi(m))\ 原根数量 \\ \varphi(m)=P_1^{\alpha_1} \cdot P_2^{\alpha_2} \cdot \cdots P_n^{\alpha_n} \\ g^{\frac {\varphi(m)} Pi} \neq 1\ (mod \ m) \\ a^{I(x)} \equiv x\ (mod \ p) \\ I(x,y)=I(x)+I(y) $$

积性函数

$$ \varphi(m)=P_1^{\alpha_1} \cdot P_2^{\alpha_2} \cdot \cdots P_n^{\alpha_n} \\ g^{\frac {\varphi(m)} Pi} \neq 1\ (mod \ m) \\ $$


$$ f(a \cdot b) =f(a) \cdot f(b) \\ gcd(a,b)=1 \\ \begin{aligned} d ( n ) & = \sum _ { i = 1 } ^ { n } 1 ( i | n ) \\ \sigma ( n ) & = \sum _ { i = 1 } ^ { n } i ( i | n ) \\ \varphi ( n ) & = \sum _ { i = 1 } ^ { n } 1 ( \operatorname { gcd } ( i , n ) = 1 ) \end{aligned} \\ \mu(n)= \begin {equation} \left\{ \begin {array} {lr} 1&n=1 \\ (-1)^k&{\prod _{ i = 1 }^k q _ { i } = 1}\\ 0&(otherwise) \end {array} \right. \end {equation}\\ \begin{array} { l } { \varepsilon ( n ) = [ n = 1 ] } \\ { I ( n ) = 1 } \\ { i d ( n ) = n } \end{array} \\ f \cdot g \\ f(n^P) \cdot f^P(n) \\ f \cdot g\\ h ( n ) = \sum _ { d | n } f ( d ) \cdot g \left( \frac { n } { d } \right) \\ (f*g)(n)=\sum _{d|n} f(d) \cdot g \left(\frac n d \right) \\ f*g=g*f \\ (f*g)*h=f*(g*h) \\ (f+g)*h=f*h+g*h \\ f * \varepsilon=f \\ \sum _{d|n} \mu(d) = [n=1] \\ \mu *I = \varepsilon $$

$$ F(n)=\sum _{d|n} f(d) \\ f(n)=\sum _{d|n} \mu(d) \cdot F\left(\frac n d \right) \\ F=f*I F*\mu = f*(I*\mu) \\ F*\mu = f * \varepsilon \\ \sum _{d|n} \frac {\mu(d)} d = \frac {\varphi(n)} n \\ \frac \varphi * (I*\mu) = \frac {id*\mu} n $$

杜教筛

$$ S(n)=\sum ^n _{i=1} f(i) \\ 时间复杂度O(n^{\frac 2 3}) \\ h=f*g $$

$$ \begin{align*} \sum ^n _{i=1} &= \sum ^n _{i=1} \sum _{d|i} g(d) \cdot f\left (\frac i d \right)\\ &= \sum ^n _{d=1} g(d) \cdot \sum _{i=1} ^{\left\lfloor \frac { n } { d } \right\rfloor} f(i) \\ &= \sum ^n _{d=1} g(d) \cdot S(\left\lfloor \frac { n } { d } \right\rfloor) \\ &=g(1) \cdot S(n) + \sum ^n _{d=2} g(d) \cdot S(\left\lfloor \frac { n } { d } \right\rfloor) \end{align*} $$

$$ S(n) =\sum _{i=1} ^n \mu(i) \\ f=\mu \\ h=f*g \\ g=I \\ h= \varepsilon \\ \mu *I = \varepsilon $$

$$ \begin{align*} S(n)&=\sum ^n _{i=1} h(i) - \sum ^n _{d=2} g(d) \cdot S(\left\lfloor \frac { n } { d } \right\rfloor) \\ &=1-\sum ^n _{d=2} S(\left\lfloor \frac { n } { d } \right\rfloor) \\ \end{align*} $$

$$ S(n)=\sum ^n _{i=1} \varphi(i)\\ \varphi *I = id $$

$$ S(n)=\sum ^n _{i=1} i \cdot \varphi(i) \\ \sum _{d|n} d \cdot \varphi(d) \cdot g \left (\frac n d \right) \\ g=id \\ \begin{align*} 上述式&=\sum _{d|n} d \cdot \varphi(d) \cdot \frac n d\\ &=\sum _{d|n} \varphi(d) \cdot n \\ &= n^2 \end{align*} $$

$$ \begin{align*} S(n) &= \sum ^n _{i=1} h(i)-\sum ^n _{d=2} g(d) \cdot S(\left\lfloor \frac { n } { d } \right\rfloor) \\ &=\sum ^n _{i=1} h^2 - \sum ^n _{d=2} d \cdot S(\left\lfloor \frac { n } { d } \right\rfloor) \end{align*} $$

STL:unordered_map

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。