约数

试除法求约数

只需枚举小于$\sqrt{n}$的约数就可求出所有约数

1
2
3
4
5
6
7
8
9
10
11

vector<int>res;
void get_div(int n){
    res.clear();
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            res.push_back(i);
            if(i!=n/i)res.push_back(n/i);//判断平方
        }
    }
    sort(res.begin(),res.end());
}

约数个数

若$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot… \cdot p_k^{\alpha_k}$

则约数个数$d(n)=(\alpha_1+1)\cdot(\alpha_2+1)\cdot…\cdot(\alpha_k+1)$

int范围内约数个数最多的数约有1600个约数。

约数之和

若$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot… \cdot p_k^{\alpha_k}$

约数之和$\sigma(n)=(p_1^0+p_1^1+…+p_1^{\alpha_1})\cdot…\cdot(p_k^0+p_k^1+…+p_k^{\alpha_k})$

欧几里得算法（辗转相除法）

性质：若$d|a，d|b$,则$d|ax+by$

定理：$(a,b)=(b,a$ $mod$ $b)$

证明：$(a,b) $$= (b,a-\lfloor \frac a b\rfloor \cdot b)=(b,a-c\cdot b)$$=(b,a$ $mod$ $b)$

实现：若$b=0$则$a$为最大公约数，否则返回$gcd(b,a%b)$

1
2
3

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