[数论](2)约数

约数

一、求约数

思路:试除法判断其是否是x的约数即可

伪码:

```C++ 给定一个x,求x的所有约数 nums数组存储所有约数,numsSize为其下标 i 从 1 开始,直到 i<=x/i 若存在[ x % i == 0 ] 则代表当前 i 是 x 的约数 将其存储下来 若存在 [ x/i != i ] 则将x / i 存储起来

(判断x/i是否等于i是因为可能两个对应的因数一样,比如4对应的两个因数2就一样)


源码:

```C++
int get_num(int x) {
    int numsSize = 0;
    for (int i = 1; i <= x / i; i++) {//因子成对出现的
        if (x % i == 0) {//若存在[ i能整除x ] 则代表 i 是 x 的约数
            nums[numsSize++] = i;//将其记录下来
            if (x / i != i) nums[numsSize++] = x / i; // 若与其成对的约数与其不同,则将其标记
        }
    }
    return numsSize;
}

二、约数个数

思路:

image-20210426005257927

伪码:

给定一个数x,求x的约数个数
    先分解质因数,定义一个Hashmap,底数做键,指数做值
    然后遍历一遍Hashmap,套用公式:ans=所有指数+1相乘

源码:

```C++

include

include

using namespace std; typedef long long LL; LL get_nums(int x) { unordered_map<int, int> prime; for (int i = 2; i <= x / i; i++) {//分解质因子 if (x % i == 0) { while (x % i == 0) { x /= i; prime[i]++;//当前i的次数加一 } } } if (x > 1) prime[x]++; LL res = 1; for (auto it : prime)//遍历Hash,套公式计算 res = res * (it.second + 1); return res; }


**约数之和**

思路:![image-20210429192603456](https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/image-20210429192603456.png)

简单来说就是 [ N的质因子阶乘相乘 ]

伪码:

```C++
给定一个正整数n,求其所有约数之和
先分解质因数,定义一个Hash表,质因子做key,次幂做val
套用公式将每个质因子求出其括号内的值
总res与括号内的值相乘
返回乘积(即为其所有约数之和)

源码:

```C++

include

include

using namespace std; typedef long long LL; LL get_sum(int x) { unordered_map<int, int> prime; for (int i = 2; i <= x / i; i++) {//分解质因子 if (x % i == 0) { while (x % i == 0) { x /= i; prime[i]++; } } } if (x > 1) prime[x]++; LL res = 1; for (auto it : prime) { int a = it.first, b = it.second;//a为底数,b为指数 LL t = 1;//括号内的和 while (b--)t = t a + 1;//将括号内的和求出来 // t = t a + 1 公式推导如下: // 第一次:1a+1 展开就是: a+1 // 第二次:a(a+1)+1 展开就是: a²a+1 // 第三次:a(a²a+1)+1 展开就是: a³a+1 res = res t;//再将括号相乘 } return res; }


**最大公约数**:

思路:gcd(a,b) = gcd(b,a mod b) 套用公式即可

源码:

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

本文链接:

https://nullcode.fun/140.html
1 + 9 =
快来做第一个评论的人吧~