数论相关

最大公约数和最小公倍数

最大公约数gcd

int gcd(int a,int b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}

最小公倍数lcm

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

质数相关结论

1.一个正整数n，最多只有一个大于根号n的质因数。(基本应用是质因数分解)
2.一个10^9次方以内的数，最多有9个不同的质因子。(这个结论往往和容斥原理结合使用)

$(2*3*5*7*11*13*17*19*23*29=6,469,693,230)$

3.素数定理

$\lim_{x\rightarrow \infty} \frac{\pi(x)}{x} = \frac{1}{\ln x}$

$\pi(x)$表示不大于x的素数个数

质数筛选法

埃拉托斯特尼筛法

const int maxm=(1e7)+5;
int Prime[maxm];
void Prepare_Prime()
{
    static bool isPrime[maxm];
    memset(isPrime,true,sizeof(isPrime));
    Prime[0]=0;                 // Prime[0]纪录有多少个质数
    for (int i=2; i<maxm; i++)
        if (isPrime[i])
        {
            Prime[++Prime[0]]=i;
            for (int j=i+i; j<maxm; j+=i) isPrime[j]=false;
        }
    printf("%d\n",Prime[0]);
}

欧拉筛选法

对[1,n]的数进行欧拉筛。

fp[i]记录i的最小质因数。(可用于质因数分解，也可判断i是否为质数)

pr[i]是质数数组，其中pr[0]为质数个数。

mu[i]为i的莫比乌斯函数，mus[i]为其前缀和。(莫比乌斯函数可以用来容斥和反演)

phi[i]为i的欧拉函数。

const int maxn=1e7+100;
int fp[maxn],pr[maxn],mu[maxn],phi[maxn],mus[maxn];
void oula_prime(int n)
{
    memset(fp,0,sizeof(fp));
    mu[1]=1;
    pr[0]=0;
    for (int i=2; i<=n; ++i)
    {
        if (!fp[i]) { pr[++pr[0]]=i,fp[i]=i,mu[i]=-1,phi[i]=i-1; }
        for (int j=1; j<=pr[0]; ++j)
        {
            int k=i*pr[j];
            if (k>n) break;
            fp[k]=pr[j];
            if (i%pr[j]==0)
            {
                mu[k]=0,phi[k]=phi[i]*pr[j];
                break;
            }
            else mu[k]=-mu[i],phi[k]=phi[i]*(pr[j]-1);
        }
    }
    mus[0]=0;
    for (int i=1; i<=n; ++i) mus[i]=mus[i-1]+mu[i];
}

质因数分解

将一个正整数n，分解成$n=p_1^{k_1}*p_2^{k_2}*...*p_m^{k_m}$($p_i$为不同质数)​的形式。

预处理试除法

一个正整数n，最多只有一个大于根号n的质因数。因此，枚举根号n以内的质数分解质因数。(以下代码质数预处理省略)

struct P_factor
{
    int p,k;
    P_factor() { p=k=0; }
    P_factor(int a,int b) { p=a,k=b; }
};
vector<P_factor> divide_factor(int x)
{
    vector<P_factor> R;
    R.clear();
    for (int i=1; i<=Prime[0]; i++)
    {
        int p=Prime[i];
        if (p*p>x) break;
        if (x%p==0)
        {
            int k=0;
            while(x%p==0) k++,x/=p;
            R.push_back(P_factor(p,k));
        }
    }
    if (x>1) R.push_back(P_factor(x,1));
    return R;
}

质因数分解形式下的gcd和lcm

$a=p_1^{k_1}p_2^{k_2}...p_m^{k_m} (k_i \ge 0)$
$b=p_1^{r_1}*p_2^{r_2}*...*p_m^{r_m} (r_i \ge 0)$
$\gcd(a,b)=p_1^{min(k_1,r_1)}*p_2^{min(k_2,r_2)}*...*p_m^{min(k_m,r_m)}$
$lcm(a,b)=p_1^{max(k_1,r_1)}*p_2^{max(k_2,r_2)}*...*p_m^{max(k_m,r_m)}$
推广到多个数，也是如此。

同余

定义和性质

定义：
给定正整数M，用M去除两个整数a和b，若余数相同，则称a和b对模M同余，记作$a\equiv b\pmod M$

性质：
自反性: $a\equiv a\pmod M$
对称性: 若$a\equiv b\pmod M$, 则$b\equiv a\pmod M$
传递性: 若$a\equiv b\pmod M$, $b\equiv c\pmod M$, 则$a\equiv c\pmod M$

加减乘运算:
若$a\equiv b\pmod M$，c为任意整数

则有

$a+c\equiv b+c\pmod M$
$a-c\equiv b-c\pmod M$
$a*c\equiv b*c\pmod M$

除法运算:
若$a\equiv b\pmod M$，c为非0整数并且gcd(c,M)=1
则有$a*inv[c]\equiv b*inv[c] \pmod M$
其中，inv[c]是c对模M的逆元，满足$c*inv[c]\equiv 1\pmod M$
推导如下:
$a/c\equiv b/c\pmod M$
$a/c*1\equiv b/c*1\pmod M$
$a/c*c*inv[c]\equiv b/c*c*inv[c]\pmod M$
$a*inv[c]\equiv b*inv[c] \pmod M$

还有一些性质可以自己找资料和推导

扩展欧几里得

上述谈到的最大公约数算法是数学家欧几里德提出的，同时，他也提出了扩展欧几里德算法来解决整数二元一次不定方程问题。

整数二元一次不定方程

形如a*x+b*y=c(a,b均不为0)的方程，a,b,c都是整数，求(x,y)的整数解。

1 判断是否有解

整数二元一次不定方程有解的充分必要是gcd(a,b)|c。如果不能整除则无解。

2 扩展欧几里德求特解

欧几里德给出了计算a*x+b*y=gcd(a,b)的解法

long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if (b==0) { x=1,y=0; return a; }
    long long d=exgcd(b,a%b,x,y);
    long long tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}

3 通解

a*x+b*y=gcd(a,b)在有解并求出特解(x,y)的情况下，通解可以表示为

$$\begin{cases} x'=x+b/gcd(a,b)*t \\ y'=y-a/gcd(a,b)*t \end{cases}$$
对于一般式a*x+b*y=c，如果有解，只需把a*x+b*y=c的特解乘上c/gcd(a,b)即可得到其特解，通解还是一样的公式。

4 例子

求出特解和一个通解

int main(int argc, char* argv[])
{
    long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    long long x,y,d;
    d=exgcd(a,b,x,y);
    if (c%d!=0) printf("No solution!\n");
    else
    {
        a/=d,b/=d,c/=d;
        x*=c,y*=c;
        printf("特解: %lld %lld\n",x,y);
        printf("一个通解: %lld %lld\n",x+b,y-a);
    }
    return 0;
}

下面两个程序，找的解满足x或y是第一个非负整数的解。

void minimal_x(long long &x,long long &y,long long &a,long long &b,long long &c)
{
    long long m=(b>0 ? b : -b);
    x%=m;
    if (x<0) x+=m;
    y=(c-a*x)/b;
}
void minimal_y(long long &x,long long &y,long long &a,long long &b,long long &c)
{
    long long m=(a>0 ? a : -a);
    y%=m;
    if (y<0) y+=m;
    x=(c-b*y)/a;
}

请思考一下，如何求出不定方程的正整数解个数。

欧拉函数

费马小定理

对于一个质数p和一个整数a，如果a和p互质，那么就有$a^{p-1}\equiv 1\pmod p$。该定理先由费马猜想，后由欧拉证明。欧拉证明的同时提出了欧拉函数。

定义

给定一个正整数n，定义$\phi(n)$等于1-n中与n互质的数的个数。对于任何整数a和n，如果a和n互质，那么就有$a^{\phi(n)}\equiv 1\pmod n$。

通式

$\phi(n)=n*\prod(1-\frac{1}{p_i})=n*\prod\frac{p_i-1}{p_i}(p_i是n的互不相同的质因子)$

不完全积性

在正整数定义域，若a和b互质，且有f(a*b)=f(a)*f(b)则称f(n)是一个积性函数(或不完全积性函数)。若对任意a,b，均有f(a*b)=f(a)*f(b)，则称f(n)是一个完全积性函数。
常见的不完全积性函数就有欧拉函数$\phi(n)$。

若有$n=a*b$且$\gcd(a,b)=1$则有$\phi(n)=\phi(a)*\phi(b)$

筛法求欧拉函数

对于一个n，我们可以用质因数分解和通式$\phi(n)=n*\prod(1-\frac{1}{p_i})$求欧拉函数。然而如果有多个欧拉函数，并且n值都不大的情况下，这样的做法效率不高。利用欧拉函数的不完全积性，我们可以用筛选法O(n)求出1-n的欧拉函数。
在看筛法之前，我们先看几条常见的公式(以下所有字母表示的都是正整数，p是质数):

1. $\phi(p)=p-1$

2. 若$n=p^k$，则$\phi(n)=(p-1)*p^{k-1}$

3. 若$n=p*a$
   

   $$\phi(n)= \begin{cases} (p-1)*\phi(a) & \text {if not p|a} \\ p*\phi(a) & \text {if p|a} \end{cases}$$

代码参考欧拉筛选法求质数

逆元

定义

如果$a*b \equiv 1\pmod M$，那么a和b互为对模M的逆元，b可以记为$a^{-1}$，反之亦然(以下记为inv[a])。
在同余部分提到过，a/b mod M 相当于a*inv[b] mod M。

逆元的求法

扩展欧几里得法

$a*b \equiv 1\pmod M$ 可化为等式 $b*a+M*y=1$

把a当成x，就相当于解二元一次不定方程。

欧拉函数法

如果a和M不互质，那么就不存在a对模M的逆元。
如果a和M互质，那么$a^{\phi(M)-1}$就是a对模M的一个逆元，特别地，当M为质数时，$a^{M-2}$就是a对模M的一个逆元。

因此，求出欧拉函数或当M为质数时，我们可以用快速幂乘法在log级别的时间复杂度内求出a对模M的逆元。

除此之外，还有一种预处理的方式求1-n对模M的逆元。

O(n)预处理法

如果M为质数，那么显然1到M-1都有对模M的逆元。假设$n<M$，那么就可以O(n)预处理出1-n对模M的逆元。

const int maxn=(1e6)+100;
int inv[maxn];
void Prepare_inv(int n,int M)
{
    inv[1]=1; //1 的逆元是1
    for (int i=2; i<=n; i++)
        inv[i]=(long long)(M-M/i)*inv[M%i] % M;
}

令$M=k*i+r (0\le r < i)$

有$k*i+r \equiv 0\pmod M$
<=> $r \equiv -k*i \pmod M$
模等号两边同时乘上r的逆元
<=> $r*inv[r]\equiv -k*inv[r]*i \pmod M$
<=> $1 \equiv -k*inv[r]*i \pmod M$

<=> $1 \equiv (M-k)*inv[r]*i \pmod M$

由逆元定义可得，$(M-k)*inv[r]$就是i的逆元。