【算法4.2】约数（完结）

目录

一、869 试除法求约数 

二、870 约数个数

三、871 约数之和

四、872 欧几里得求最大公约数

---

一、869 试除法求约数 

活动 - AcWing

void get_div(int x)
{
    vector<int>res;
    for(int i=1;i<=x/i;i++)
        if(x%i==0)
        {
            res.push_back(i);
            if(i!=x/i) res.push_back(x/i); //如果不是平方数 就把它配对的数也放进去
        }
    sort(res.begin(),res.end());
    for(auto t:res) cout<' ';
    puts("");
}

二、870 约数个数

活动 - AcWing

#include 
#include 
using namespace std;
 
typedef long long LL;
const int mod=1e9+7;
 
int main()
{
    unordered_map<int,int>primes;//存储所有的底数和指数
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
            while(x%i==0)
            {
                x/=i;
                primes[i]++;
            }
        if(x>1) primes[x]++;
    }
    LL res=1;
    for(auto x:primes) res=res*(x.second+1)%mod;
    cout<
    return 0;
}

 

三、871 约数之和

活动 - AcWing

#include 
#include 
using namespace std;
 
typedef long long LL;
const int mod=1e9+7;
 
int main()
{
    unordered_map<int,int>primes;//存储所有的底数和指数
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
            while(x%i==0)
            {
                x/=i;
                primes[i]++;
            }
        if(x>1) primes[x]++;
    }
    LL res=1;
    for(auto x:primes)
    {
        LL a=x.first,b=x.second;
        LL t=1;
        while(b--) t=(t*a+1)%mod;
        res=res*t%mod;
    }
    cout<
    return 0;
}

 

四、872 欧几里得求最大公约数

 活动 - AcWing

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