试除法求约数

$O(\sqrt{n})$

vector<int>q;
void m0(int n){
    for(int i=1;i<n/i;i++){
        if(n%i==0){
            q.push_back(i);
            if(i!=n/i) q.push_back(n/i);
        }
    }
}

约数个数

$$A= \prod {P_i}^{a_i}$$

其中$P_i$全部为质数
则$A$的约数个数:
$$N= \prod ({a_i}+1)$$
直接在分解质因数（上一篇模板）的代码上进行修改即可。

unordered_map<int,int> mp;
int m0(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            while(n%i==0){
                mp[i]++;
                n/=i;
            }
        }
    }
    if(n!=1) mp[n]++;

    long long int res=1;

    //使用迭代器对mp进行遍历
    unordered_map<int,int>::iterator it=mp.begin();
    while(it!=mp.end()){
        int a=it->first,b=it->second;
        res=res*(b+1);
        it++;
    }
    return res;
}

⭐⭐
题目要求n个数的乘积的约数个数，可以求出来分别求出来每个数的约数（下一个数直接在之前有的约数个数上进行累加），最后再用公式进行计算就可以了

约数和

$$N= \prod_{i = 1} ^{n} {P_i}^{a_i}$$

其中$P_i$全部为质数
则$A$的约数和:
$$S= \prod_{i = 1} ^{n} \sum_{j = 0} ^{a_i} {P_i}^j$$

const int mod=1e9+7;
unordered_map<int,int> mp;
int m0(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            while(n%i==0){
                mp[i]++;
                n/=i;
            }
        }
    }
    if(n!=1) mp[n]++;

    long long int res=1;

    unordered_map<int,int>::iterator it=mp.begin();
    while(it!=mp.end()){
        int a=it->first,b=it->second;

        long long int temp=1,cnt=0;
        for(int i=0;i<b;i++){
            temp*=a;
            cnt+=temp;
        }
        res=res*(cnt+1)%mod; //取模为题目要求

        it++;
    }
    return res;
}

最大公约数

$O(logn)$

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