各种线性筛法（积性函数）

前提\(n=\prod_{i=1}^kp_i^{a_i}\)

素数

第一准则：每个合数一定会被它的最小质因子筛掉。

欧拉函数

定义式 \(\phi_n=\prod_{i=1}^k(1-\frac{1}{p_i})(n>2)\space\phi_1=1\)
积性函数性质\(\phi_{x\cdot y}=\phi_x\cdot\phi_y(gcd(x,y)=1)\)
性质一 \(\phi_p=p-1\)
性质二 \(\phi_{p^k}=(p-1)p^{k-1}\)
性质三 \(\sum_{i=1}^{n-1}[gcd(i,n)=1]\cdot i=\frac{\phi_n*n}{2}\)
性质四 \(\sum_{d|n}\phi_d=n\)(莫比乌斯反演里有用)

莫比乌斯函数

定义式\[\mu_n= \begin{cases} 1 &\text{n=1}\\ (-1)^k & \text{$\prod_{i=1}^ka_i=1$}\\ 0 & \text{$\prod_{i=1}^ka_i>1$}\ \end{cases}\]
定理\[\sum_{d|n}\mu_{d}=\left[n=1\right]=\begin{cases}1&\text{n=1,}\\ 0 &\text{$n>1$.} \end{cases}\]
证明:对于\(n=1\)，等式显然成立.对\(n>1\),在\(\sum_{d|n}\mu(d)\) 中非零的项仅来自于\(d=1\)与\(n\)的约数是不同素数的乘积，即
\[\begin{aligned} \sum_{d|n}\mu_{d}={}& \mu_1+\mu_{p_1}+…+\mu_{p_k}+\mu_{p_1p_k}+…+{} \\ &\mu_{p_{k-1}p_k}+…+\mu_{p_1p_2…p_k}{}\\ ={}&1+\binom{k}{1}(-1)+\binom{k}{2}(-1)^2+…+\binom{k}{k}(-1)^k{}\\ ={}&0 \end{aligned}\]

\\混合
inline void Seg_Shai(void){
    re int i,j;
    mu[1]=1;phi[1]=1;
    for(i=2;i<=n;++i){
        if(!vis[i]){pri[++*pri]=i;mu[i]=1;phi[i]=i-1;}
        for(j=1;j<=*pir;++j){
            if(i*pri[j]>n)break;
            if(!(i%pri[j])){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            mu[i*pri[j]]=-mu[i];phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
} 

约数分解(\(Pollar\space Pro\))

\(gcd(exgcd)\)

$\gcd(a,b) = ax+by\
b\neq 0 \implies \gcd(a,b) = \gcd(b,a\bmod b)\
bx'+(a\bmod b)y' = \gcd(b,a\bmod b)\
ax+by = bx'+(a\bmod b)y'\
\because a\bmod b = a-\lfloor\frac a b\rfloor b\
\therefore ax+by = bx'+( a-\lfloor\frac a b\rfloor b)y'\
\therefore ax+by = ay'+b(x'-\lfloor\frac a b\rfloor y')\
x = y',y = x' - \lfloor\frac a b\rfloor y'
$

//gcd
inline gcd(re int a,e int b){return b?gcd(b,a%b):a;}
//exgcd
inline int exgcd(re int a,re int b,re int&x,re int&y){
    re int tmp,res;
    if(!b){x==1;y==0;return a;}
    res=exgcd(b,a%b,x,y);
    tmp=x;x=y;y=tmp-y*(a/b);
    return res;
}

\((ex)CRT\)

求解\(\left\{ \begin{array}{c}x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod{m_2} \\ x\equiv a_3\pmod {m_3}\\\cdots\\x\equiv a_k\pmod {m_k}\end{array}\right.\)其中\((m_i,m_j)=1,1\le i\neq j\le k\)
解:
设\(\displaystyle{M=\prod_{i=1}^km_k}\)；
则\(x=(\sum\limits_{i=1}^k a_i*{M\over m_i}*({M\over m_i})^{-1}\pmod {m_i})\mod M\)

//CRT
inline void exgcd(re int a,re int b,re int&x,re int&y){
    if(!b){x=1;y=0;return ;}
    exgcd(b,a%b,x,y);
    re int tmp=x;x=y;y=tmp-(a/b)*y;
}
inline int CRT(void){
    re int i,M=1,x,y,rest,ans=0;
    for(i=1;i<=k;++i)M*=m[i];
    for(i=1;i<=k;++i){
        rest=M/m[i];
        exgcd(rest,m[i],x,y);
        x=(x%m[i]+m[i])%m[i];
        (ans+=rest*x%M*a[i]%M)%=M;
    }
    return (ans+M)%M;
}

置换群

0.群
\((G,*)\),表示一个元素为\(G\)集合，有\(*\)二元运算的群
其性质有结合律，有单位元，有逆元，封闭性
1.置换
我们记\(\displaystyle{\begin{pmatrix}a_1&a_2&a_3&\cdots&a_n\\b_1&b_2&b_3&\cdots& b_n\end{pmatrix}}\)表示将\(a_1\)换为\(b_1\),\(a_2\)换为\(b_2\cdots\)以此类推,注意一个置换是一种操作
【性质】一个\(n\)的排列有\(n!\)个置换
2.循环
循环是一种特殊的置换，如果我们将\(i\)向\(a_i\)连一条有向边，就会出现环
记为\((a_1,a_2,a_3,\cdots,a_n)=\displaystyle{\begin{pmatrix}a_1&a_2&a_3&\cdots&a_n\\a_2&a_3&a_4&\cdots&a_1\end{pmatrix}}\)
3.Burnside
本质上是去重计数
【公式】\(ans\)=\(\frac{\sum_{f\in G} C(f)}{|G|}\)
其中\(G\)表示操作的集合,\((G,\)使用操作\()\)是一个群,\(f是G中一个操作\)
\(C(f)\)表示在\(f\)作用下的等价类大小