【数论】约数

文章目录

• ​​一、试除法求n的所有约数​​
• ​​二、约数个数​​
• ​​三、约数之和​​
• ​​四、最大公约数（欧几里得算法/辗转相除法）​​

一、试除法求n的所有约数

vector<int> getDivisors(int n) {
  vector<int> ans;
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      ans.push_back(i);
      if (i != n / i) {
        ans.push_back(n / i); // n == n/i，只需要存一个
      }
    }
  }
  return ans;
}

时间复杂度：

二、约数个数

约数和质因子并不是一个意思，但每个约数可以表示成质因子的乘积

算数基本定理：的约数个数为：，为质因子

例子：，12的约数有1,2,3,4,6,12共6个，根据公式计算同样是个

n的每个约数m都可以表示成的形式，，每个有种选法，于是就有个因数

我们分解质因子后，获取质因子的指数，最后套用即可

int getDivisorsNum(int n) {
  vector<int> nums;
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      int num = 0;
      while (n % i == 0) {
        n /= i;
        num++;
      }
      // 获取质因子的指数
      nums.push_back(num);
    }
  }
  if(n > 1) nums.push_back(1);
  int ans = 1;
  for (int num : nums) {
    ans *= (num + 1);
  }
  return ans;
}

三、约数之和

例子：，12的约数有1,2,3,4,6,12，约数之和为28，根据公式计算同样是个

其中，，一直循环n次

int getDivisorsSum(int n) {
  const int mod = 1e9 + 7;
  unordered_map<int, int> primes;
  for (int i = 2; i <= n / i; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
        primes[i]++;
      }
    }
  }
  if (n > 1) primes[n] = 1;
  
  long long ans = 1;
  for (auto prime : primes) {
    int p = prime.first;
    int n = prime.second;
    // 计算sum = p^0 + p^1 + p^2 + ... + p^n
    long long sum = 1;
    while (n >= 1) {
      sum = (sum * p + 1) % mod;
      n--;
    }
    ans = ans * sum % mod;
  }
  return ans;
}

四、最大公约数（欧几里得算法/辗转相除法）

如果d是a的约数，也是b的约数，则d是ax+by的约数，则有：，

比如a=24，b=18，那么gcd(24,18)=6，gcd(18,24%18)=6

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

时间复杂度为