约数

$d$能整除$n$，则称$d$是$n$的约数

算术基本定理的两个推论

由算术基本定理：任何一个大于$1$的正整数都能唯一分解成有限个质数的乘积，可写作：$N={p_1}^{c_1}{p_2}^{c_2}\cdots {p_m}^{c_m}$
其中$c_i$都是正整数，$p_i$都是质数，且$p_1<p_2<\cdots <p_m$
可以知道$N$的每个正约数都可以写成${p_1}^{b_1}{p_2}^{b_2}\cdots {p_m}^{b_m}$，其中$0\leq b_i\leq c_i$
再由乘法原理可知，$N$的正约数个数为$(c_1+1)(c_2+1)\cdots (c_m+1)$
$N$的所有正约数之和为$(1+p_1+p_1^2+\cdots p_1^{c_1})\cdots (1+p_m+p_m^2+\cdots p_m^{c_m})$

求$N$的正约数集合

试除法

由于约数总是成对出现(除了对于完全平方数，$\sqrt N$会单独出现)，只需扫描$1$~$\sqrt N$，看是否能整除$N$即可

void getfactor(int n)
{
    m = 0;
    for (int i = 1; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            factor[++m] = i;
            if (i != n / i)
                factor[++m] = n / i;
        }
    }
}

试除法推论

一个整数$N$的约数个数上界为$2\sqrt N$

求$1$~$N$每个数的正约数集合

倍数法

对于每个数$d$，$1$到$N$中以$d$为约数的数就是$d$的倍数

vector<int> factor[N]; // factor[i]里存i的正约数集合
void getfactor(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n / i; j++)
            factor[i * j].push_back(i);
}

倍数法推论

$1$到$N$每个数的约数个数的总和大约为$NlogN$
相关题有： 反素数 余数之和

最大公约数

定理： $gcd(a,b)\times lcm(a,b)=a\times b$
九章算术.更相减损术：$\forall a,b\in N，a\geq b，有gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)$
欧几里得算法：$\forall a，b\in N,b\neq 0，gcd(a,b)=gcd(b,a$%$b)$

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

由于高精度取模不容易实现，需要用高精度运算时，一般用更相减损术代替欧几里得算法
相关题有： Hankson的趣味题

互质与欧拉函数

若$gcd(a，b)=1$，则称$a$，$b$互质
若$gcd(a，b，c)=1$，则称$a$，$b$，$c$互质
若$gcd(a，b)=gcd(a，c)=gcd(b，c)=1$，则称$a$，$b$，$c$两两互质
欧拉函数：$1$到$N$中与$N$互质的数的个数被称为欧拉函数，记为$\varphi (N)$
若在算术基本定理中，：$N={p_1}^{c_1}{p_2}^{c_2}\cdots {p_m}^{c_m}$，则：
$\varphi (N)=N\times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_m-1}{p_m}$
证明：利用容斥原理，得到$1$到$N$中不与$N$含有任何共同质因子的数的个数(就是与$N$互质的数的个数)
根据计算式，只需分解质因数就可以顺便求出一个数的欧拉函数

int phi(int n)
{
    int ans = n;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

利用线性筛$O(N)$求出$2$到$N$每个数的欧拉函数(利用下面提到的性质$3$和$4$)

int v[N], prime[N], phi[N], m;
void euler(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == 0)
        {
            v[i] = i, prime[++m] = i, phi[i] = i - 1;
        }
        for (int j = 1; j <= m; j++)
        {
            if (prime[j] > v[i] || prime[j] > n / i)
                break;
            v[i * prime[j]] = prime[j];
            phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
        }
    }
}

欧拉函数的性质：
$1$.$\forall n>1，1$~$n$中与$n$互质的数的和为$\frac{n\times \varphi (n)}{2}$
$2$.若$a$，$b$互质，则$\varphi (ab)=\varphi(a)\varphi(b)$
$3$.设$p$为质数，若$p\mid n$且$p^2\mid n$，则$\varphi (n)=\varphi(\frac{n}{p})\times p$
$4$.设$p$为质数，若$p\mid n$但$p^2\nmid n$，则$\varphi (n)=\varphi(\frac{n}{p})\times (p-1)$
$5$.$\sum_{d\mid n}{\varphi (d)}=n$
性质$1$证明：
根据更相减损术，$gcd(n,x)=gcd(n,n-x)$，所以与$n$不互质的数是成对出现的，并且它们的平均值是$\frac{n}{2}$，因此，与$n$互质的数的平均值也是$\frac{n}{2}$
性质$2$证明：
直接按欧拉函数计算式展开即可，等式两边是相等的
剩下三个证明有点难记，有需要见蓝书就好
相关题有： 可见的点

积性函数

若当$a$，$b$互质时，有$f(ab)=f(a)\times f(b)$，那么称$f$为积性函数
性质：若$f$是积性函数，且在算术基本定理中$N={p_1}^{c_1}{p_2}^{c_2}\cdots {p_m}^{c_m}$，则$f(N)=f({p_1}^{c_1})f({p_2}^{c_2})\cdots f({p_m}^{c_m})$