[编程笔记]-Divisor_Basis约数基础

概念

x的约数其实就是能整除x的正整数。

例：4的约数有{1,2,4}。

求约数。

对，没错，还是试除法。

不会可以看看质数基础（？）
[编程笔记]-Prime_Basis质数基础

O(sqrt(n))

vector<int> get_dvs(int num){
    vector<int> res;
    for(int i=1;i<=num/i;i++){
        if(num%i==0){
            res.push_back(i);
            if(num/i!=i)res.push_back(num/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}

约数个数

公式

算数基本定理：
N=P1^a1P2^a2…*Pk^ak

那么N的约数个数是(a1+1)(a2+1)…(ak+1)

证明：

令d为N的约数，则有

d=P1^b1P2^b2…*Pk^bk

(0<=bi<=ai)

就是分解质因数
[编程笔记]-Prime_Basis质数基础

所以枚举所有情况就好了。每一个b都有(a+1)种情况，然后乘法定理。

例题

AcWing870-约数个数
由于公式是乘法，题目要求中也是乘法，就相当于看作同一个数了。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod=1e9+7;

int n,a;
ll ans=1;
unordered_map<int,ll> mp;

int main(){
    cin>>n;
    while(n--){
        cin>>a;
        for(int i=2;i<=a/i;i++){
            while(a%i==0){
                a/=i;
                mp[i]++;
            }
        }
        if(a>1)mp[a]++;
    }
    for(auto p:mp){
        ans=ans*(p.second+1)%mod;
    }
    cout<<ans;
    return 0;
}

约数之和

(p1⁰+p1¹+p1²+…+p1^a1)…(pk⁰+pk¹+pk²+…+pk^ak)

把这个公式展开，就是所有情况的约数相加了。

求上面那个公式：
重复a次t=p*t+1

t初始为1

1. t=p+1
2. t=p²+p+1
3. t=p³+p²+p+1
   …

然后就没有然后了

AcWing871-约数之和

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod=1e9+7;

int n,a;
ll ans=1;
unordered_map<int,ll> mp;

int main(){
    cin>>n;
    while(n--){
        cin>>a;
        for(int i=2;i<=a/i;i++){
            while(a%i==0){
                a/=i;
                mp[i]++;
            }
        }
        if(a>1)mp[a]++;
    }
    for(auto pa:mp){
        int p=pa.first,a=pa.second;
        ll t=1;
        while(a--)t=(t*p+1)%mod;
        ans=ans*t%mod;
    }
    cout<<ans;
    return 0;
}

最大公约数——欧几里得算法

简介

欧几里得算法（Euclidean Algorithm），也叫辗转相除法（是不是熟悉多哩(￣︶￣)），主要用来解决最大公约数（最大公因数）问题。

tips: __gcd()应该也是用这个的吧

算法

gcd(a, b)=gcd(b, a%b)

若d|x, d|y, 则d|ax+by

a%b==a-c*b

令a,b最大公约数为d1，则d1|a, d1|b, 所以d1|a-c*b，即d1|a%b。

令b,a%b最大公约数为d2，则d2|b, d2|a-c*b, 所以d2|a-c*b+c*b，即d2|a。

因此，二者的公约数全部相同，最大公约数也相同。

特殊但其实不特殊地，当b==0时，最大公约数是a，因为0可以被任何数整除都余0。

代码

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

完结撒花o(￣︶￣)o

骚年，你已经打开了通往数论的大门，走上了这条不归路了（〒▽〒）