约数问题

求约数

vector<int> y(int x)
{
    vector<int>ans;
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)//能整除，为一个约数
        {
            ans.push_back(i);//加入答案
            if(i!=x/i) ans.push_back(x/i);//防止加入相同的约数。
        }
    }
    sort(ans.begin(),ans.end());
    return ans;
}

求约数个数

基本概念:

1.算术基本定理:任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。
2.约数定理：一个数分解成有限个质因数的乘积，设质因数指数为a1,a2,a3….
则约数的总个数为（a1+1)(a2+1)(a3+1)……。有乘法定理即可简单理解。
代码：

#include<bits/stdc++.h>
using namespace std;
const int mod =1e9+7;
int n;
int main(void)
{
    scanf("%d",&n);
    unordered_map<int,int>map;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                x/=i;
                ++map[i];//记录每个质因数的指数
            }
        }
        if(x>1) ++map[x];
    }
    long long ans =1;
    for(auto&m:map)
    {
        ans = ans*(m.second+1)%mod;//相乘。
    }
    cout<<ans<<endl;
}

求约数之和

约数和定理：
对于一个大于1正整数n可以分解质因数：n=p1^a1p2^a2p3^a3…pk^ak,
那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为
f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）。
代码：

#include<bits/stdc++.h>
using namespace std;
const int mod =1e9+7;
int n;
int main(void)
{
    scanf("%d",&n);
    unordered_map<int,int>map;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
        {
            while(x%i==0)
            {
                x/=i;
                ++map[i];
            }
        }
        if(x>1) ++map[x];
    }
    long long ans =1;
    for(auto&m:map)
    {
        int p = m.first;
        int a = m.second;
        long long t =1;
        while(a--) t= (t*p+1)%mod;//秦九韶算法，计算 p0+.....+pk。
        ans = (ans*t)%mod;
    }
    cout<<ans<<endl;
}

最大公约数

扩展欧几里的算法
gcd(a,b)=gcd(b,a%b)
代码：

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