算法笔记第五章代码模板总结
此篇文章主要参考了《算法笔记》 上面的代码模板以及acwing算法基础课 中的代码模板。

最大公约数与最小公倍数
1.最大公约数
原理：辗转相除法

int gcd(int a, int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}

或者

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

2.最小公倍数
先求出最大公约数，然后两数相乘除以最大公约数即可

int d=gcd(a,b);
int res=a/d*b;   //这么写是为了防止a*b溢出

分数
ACWING1578/PAT1088
1.分数的表示
使用结构体表示

struct Fraction{
  int up,down;   //为了防止溢出，可以将int改成long long,为了方便，以下代码都使用int    
};

2.分数的化简
原则：
若分数为负数，则分子为负数，分母为正数
若分子为0，令分母等于1
若分子不为0，令分子分母除以分子分母绝对值的最大公约数

Fraction reduction(Fraction r){
    if(r.down<0){
        r.up=-r.up;
        r.down=-r.down;
    }

    if(r.up==0)
        r.down=1;
    else{
        int temp=gcd(abs(r.up),abs(r.down));
        r.up/=temp;
        r.down/=temp;
    }
    return r;                      //最后一步不要忘记返回r
}

3.分数的四则运算
加法

Fraction add(Fraction x, Fraction y){
    Fraction res;
    res.up=x.up*y.down + x.down*y.up;
    res.down=x.down*y.down; 
    return reduction(res);
}

减法

Fraction sub(Fraction x, Fraction y){
    Fraction res;
    res.up=x.up*y.down - x.down*y.up;
    res.down=x.down*y.down;
    return reduction(res);  
}

乘法

Fraction mul(Fraction x, Fraction y){
    Fraction res;
    res.up=x.up*y.up;
    res.down=x.down*y.down;
    return reduction(res);
}

除法

Fraction divide(Fraction x, Fraction y){
    Fraction res;
    res.up=x.up*y.down;
    res.down=x.down*y.up;
    return reduction(res);
}

4.分数的输出
原则：
如果分母等于1，输出分子
如果为假分数，将其转换为真分数。注意：判断假分数的时候，是比较分子的绝对值跟分母的绝对值大小。
如果为真分数，直接输出分子/分母

void showResult(Fraction r){
    r=reduction(r);
    if(r.down==1) cout<<r.up;
    else if(abs(r.up) > abs(r.down)) printf("%lld %lld/%lld",r.up/r.down,abs(r.up)%r.down,r.down);
    else{
        printf("%lld/%lld",r.up,r.down);
    }
}

质数
1.判断质数

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

2.使用筛法(朴素筛法)生成素数表

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

3.质因子分解

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

高精度
1.高精度加法

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0,t=0; i < A.size()||i<B.size()||t; i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

2.高精度减法
使用cmp函数判断a,b的大小，让大的数减小的数

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();

    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

3.高精度乘法
要去除前导零，样例a=12345,b=0

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    for (int i = 0,t=0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    //去除前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

4.高精度除法

vector<int> div(vector<int> &A, int b, int &r) 
{
    vector<int> C;                                     //b为除数，r为余数
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());                     //为了跟前面加减除法输出格式一样，需要翻转一下
    while (C.size() > 1 && C.back() == 0) C.pop_back();  //去除前导零
    return C;
}