1.核心思想

1. 质数判断：试除法
2. 约数个数：任何一个数 n ，一定能够表示成 n = a0^p0 * a1^p1 * a2^p2 ... ak^pk, 其中 a0,a1,a2...ak都是质数，那么数 n的所有约数个数 T = (1+p0)(1+p1)(1+p2)...(1+pk)
3. 约数之和: 任何一个数 n ，一定能够表示成 n = a0^p0 * a1^p1 * a2^p2 ... ak^pk, 其中 a0,a1,a2...ak都是质数，那么数 n的所有约数之和

S = (a0^0 + a0^1 + a0^2 + ... a0^p0) * (a1^0 + a1^1 + a1^2 + ... a1^p1) * (a2^0 + a2^1 + a2^2 + ... a2^p2)...(ak^0 + ak^1 + ak^2 + ... ak^pk)

1. 最大公约数：

gcd(a, b) = gcd(b, a mod b)

2. 代码模板

1. 约数
for(int i = 1; i <= a / i; i++){
    if(a % i == 0){
        int b = a / i;
        if(b == i){
            printf("%d ", i);
        } else {
            printf("%d %d", i, b);
        }
    }
}

2. 约数个数
LL ans = 1;
unordered_map<int,int> hash;
cin >> x;
for(int i = 2;i <= x/i; ++i){
    while(x % i == 0){
        x /= i;
        hash[i] ++;
    }
}
if(x > 1) hash[x] ++;

for(auto i : hash) ans = ans*(i.second + 1) % mod;
cout << ans;

3. 约数之和
LL ans = 1;
unordered_map<int,int> hash;
cin >> x;
for(int i = 2;i <= x/i; ++i){
    while(x % i == 0){
        x /= i;
        hash[i] ++;
    }
}
if(x > 1) hash[x] ++;

for(auto i : hash){
    LL temp = 0;
    LL subSum = 0;
    for(int j = 0; j <= i.second; j++){
        if(j == 0){
            temp = 1;
            subSum = 1;
        } else {
            temp = temp * i.first % mod;
            subSum = subSum + temp % mod;
        }
    }
    ans = ans * (subSum % mod) % mod;
}

4. 最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}