试除法求约数O(sqrt(n))

• 通过枚举较小的约数，并计算出成对的较大的约数

  vector<int> get_divisors(int n)
  {
    vector<int> res;
    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());
    return res;
  }

  约数个数和约数之和

• 把一个数进行质因子分解，，对于每一项，都有种选择

• 因此，约数个数为
• 因此，约数之和为

  约数个数

  ```cpp

  include

  include

  using namespace std;

typedef long long LL; const int mod = 1e9 + 7;

int main() { int n; unordered_map hash; cin >> n; while (n —) { int x; cin >> x; // 质因子分解 for (int i = 2; i <= x / i; i ++) { while (x % i == 0) { hash[i] ++; x /= i; } } if (x > 1) { hash[x] ++; } } // 这个地方需要用long long，因为乘积可能溢出 LL ans = 1; for (auto kv: hash) { ans = ans * (kv.second + 1) % mod; } cout << ans << endl; return 0; }

<a name="tbOTP"></a>
#### [约数之和](https://www.acwing.com/problem/content/873/)
```cpp
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
    int n;
    unordered_map<int, int> hash;
    cin >> n;
    while (n --) {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i ++) {
            while(x % i == 0) {
                hash[i] ++;
                x /= i;
            }
        }
        if (x > 1) {
            hash[x] ++;
        }
    }
    LL ans = 1;
    for (auto kv: hash) {
        int k = kv.first, v = kv.second;
        LL p = 1;
        for (int i = 0; i < v; i ++) {
            p = (p * k + 1) % mod;
        }
        ans = (ans * p) % mod; 
    }
    cout << ans << endl;
    return 0;
}

最大公约数

• 根据约数的定义可知，如果d能整除a并且d能整除b，则d能整除(xa + yb)
• 欧几里得定理gcd(a, b) == gcd(b, a % b)
• 证明，a % b = a - (a / b) b，由于a, b均为整数，因此a / b为整数，因此a % b = a - c b
• 对于a, b的公约数d，则d能整除a % b = a - c * b
• 反之亦然，对于b, a % b的公约数d，d能整除a = a - c b + c b ```cpp

  include

  using namespace std;

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

int main() { int n; scanf(“%d”, &n); while (n —) { int a, b; scanf(“%d%d”, &a, &b); cout << gcd(a, b) << endl; } return 0; } ```