1.试除法求一个数的所有约数

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;
}

2.约数个数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>


using namespace std;

typedef long long LL;

const int mod = 1e9+7; 
int n;

int main()
{
    scanf("%d",&n);
    unordered_map<int,int> primes;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                x/=i;
                primes[i]++;
            }
            //printf("****%d\n",x);
        }
        //printf("***%d\n",x);
        if(x>1)
            primes[x]++;
    }
    LL res=1;
    for(auto prime:primes)
    {
        //printf("%d***\n",prime.second+1);
        res=res*(prime.second+1)%mod;
    }
    printf("%lld\n",res);
    return 0;
}

3.约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>


using namespace std;

typedef long long LL;

const int mod = 1e9+7; 
int n;


int main()
{
    scanf("%d",&n);
    unordered_map<int,int> primes;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                x/=i;
                primes[i]++;
            }
            //printf("****%d\n",x);
        }
        //printf("***%d\n",x);
        if(x>1)
            primes[x]++;
    }
    LL res=1;
    for(auto prime:primes)
    {
        int p=prime.first,a=prime.second;
        LL t=1;
        while(a--)
            t=(t*p+1)%mod;
        res=res*t%mod;
    }
    printf("%lld\n",res);
    return 0;
}

/*
1
p+1
p^2+p+1
p^3+p^2+p+1
*/

4.最大公约数(欧几里得算法、辗转相除法)

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