[数论](2)约数

约数

一、求约数

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

伪码:

给定一个x,求x的所有约数
nums数组存储所有约数,numsSize为其下标
    i 从 1 开始,直到[ i<=x/i ](因数是成对出现的,我们只需枚举小的哪一个即可)
        若存在[ x % i == 0 ] 则代表当前 i 是 x 的约数
            将其存储下来
            若存在 [ x/i != i ] 则将x / i 存储起来

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

源码:

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相乘

源码:

#include<iostream>
#include<unordered_map>
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

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

伪码:

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

源码:

#include<iostream>
#include<unordered_map>
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 公式推导如下:
           // 第一次:1*a+1          展开就是: a+1
           // 第二次:a(a+1)+1       展开就是: a²*a+1
           // 第三次:a(a²*a+1)+1    展开就是: a³*a²*a+1
        res = res * t;//再将括号相乘
    }
    return res;
}

最大公约数

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

源码:

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

本文链接:

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