数论的算法实现

数论

搬运自好友：therainisme的博客

试除法判定质数

就从2开始除，如果不能被整除就继续除，直到$\sqrt n$为止，也就是说，直到$i*i\leq n$为止

bool check(int x){
    if(x < 2) return false;
    else{
        for(int i =2;i<= x/i;i++){
            if(x%i==0) return false;
        }
    }
  	return true;
}

分解质因素

void divide(int x)
{	// 第一个数是质因数，第二个数是质因数的个数
    for (int i = 2; i <= x / i; ++i)
    { // 从小到大的去取质数，稳
        // i表示的是质数
        if (x % i == 0)
        { // 如果是质因数
            // 这个质数需要多少个
            int cnt = 0; // 求其指数
            // 除x直到除不了为止
            while (x % i == 0)
            {
                cnt++;
                x /= i;
            }
            cout << i << " " << cnt << endl;
        }
    }
    // 在这里如果 x > 1,说明还剩下一个大于大于 sqrt(x) 的因数
    if (x > 1)
        cout << x << " " << 1 << endl;
}

试除法求所有因数

vector<int> v;//用于存储因数
void divide(int x){
    for(int i =1;i<=x/i;i++){
        // 找到一组因数
        if(x%i == 0){
            v.push_back(i);
            // 确保两个因素不相同
            if(x/i != i)
                v.push_back(x/i);
        }
    }
    sort(v.begin(),v.end());
}

约数个数

本质就是对质因数的不同指数形式的全排列

map<int,int>cnt;
map<int,int>::iterator it;
// 求x的因素指数
void divide_sum(long long x){
    for(long long i = 2;i<=x/i;i++){
        while(x%i==0){
            cnt[i]++;
            x/=i;
        }
    }
    if(x>1)cnt[x]++;
}
// map中存放了质因数和对应的指数
// 因数的个数
long long get_res(){
    long long res = 1;
    for(it = cnt.begin();it != cnt.end();it++){
        // 这里+1是因为还有指数为0的选择
        res = res*(it->second+1)%MOD;
    }
    return res;
}

约数之和

本质上可以利用质因素进行计算求和结果T，如下公式会比较清晰,$a_1,a_2,...,a_n$表示不同的质因数

$$T = (a_1^0+a_1^2+...+a_1^k)\times(a_2^0+a_2^2+...+a_2^k)\times...\times(a_n^0+a_n^2+...+a_n^k)$$

举个栗子，该栗子可以用于求解每一个括号中的内容：

$$T = 1 + 2^1+2^2+2^3\\ =1+2\times(1+2^1+2^2)\\ =1+2\times(1+2\times(1+2))$$

// 求解质因数的结果同上
// 求因素之和
long long get_res(){
    long long res = 1;
    for(it = cnt.begin();it != cnt.end();it++){
        // p是质因数，e是对应的指数
        int p = it->first;
        int e = it->second;
        // 开始求一个括号中的结果
        long long t = 1;
        while(e--)t = (t*p+1) % MOD;
        res = res *t %MOD;
    }
    return res;
}

// 快速幂
// a表示底数，k表示指数
int qmi(int a,int k){
    int res = 1;
    a%=mod;
    while(k){
        if(k&1)res = res*a%mod;
        a=a*a%mod;
       	k>>=1;
    }
    
}


// 求一个括号中的内容可以用下面这个函数表示：
// a表示底数，k表示最大指数
int sum(int a,int k){
    if(k==0)return 1;
    if(k%2==0)return (1+a%mod*sum(a,k-1))%mod;
    return (1+qmi(a,k/2+1))*sum(a,k/2)%mod;
}

最大公约数和最小公倍数

gcd(a,b)求的是最大公约数，

a*b/gcd(a,b)求的是最小公倍数

本质是辗转相除法的递归写法

1个字，妙啊

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