数论算法

2021-01-12

最大公约数

在这里插入图片描述

最小公倍数

在这里插入图片描述

分数四则运算

1.分数的表示
在这里插入图片描述
2.分数的化简

3.分数的加法

4.分数的减法

5.分数的乘法

6.分数的除法
分数的输出

质因子分解

在这里插入图片描述 )

#include<bits/stdc++.h>

using namespace std;
//质因子分解
struct factor{
    int x;//素数
    int cnt;//素数出现的次数
}fac[10];
vector<int> prime;
bool isprime[10010];

void init_prime(){
    fill(isprime,isprime+10010,true);
    isprime[0]=false;
    isprime[1]=false;
    for(int i=2;i<10010;i++){
        if(!isprime[i]) continue;
        else{
            prime.push_back(i);
            for(int j=i*i;j<10010;j+=i){
                isprime[j]=false;
            }
        }
    }
}

int main(){
    int n;
    cin>>n;
    int index=0;
    init_prime();
    for(int i=0;prime[i]<sqrt(n);i++){
        if(n%prime[i]==0){
            fac[index].x=prime[i];
            fac[index].cnt=1;
            n/=prime[i];
            //如果还是能除得尽当前的素数就继续除
            while(n!=0&&n%prime[i]==0){
                fac[index].cnt++;
                n/=prime[i];
            }
            index++;
        }
    }
    //最后可能存在的一个超过sqrt(n)的素数
    if(n!=0){
        fac[index].x=n;
        fac[index].cnt=1;
        index++;
    }
    for(int i=0;i<index;i++){
        for(int j=fac[i].cnt;j>0;j--){
            cout<<fac[i].x<<'*';
        }
    }
}

n!质因p的个数

在这里插入图片描述

组合数

相当于组合数公式的变形，对于$C^{m}_{n}$来说
相当于 后m个的乘积/前m个的乘积
但注意乘和除一定同步进行，不然可能在中途溢出
在这里插入图片描述

高精度运算

任意门

快速幂

任意门