数论--基本工具（gcd 快速幂 快速乘）

参考引用链接：
gcd
快速乘/快速幂(+取模)
一：gcd：
(1)求最大公约数也可利用它来求最小公倍数

递归算法：
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
循环算法：
ll gcd(ll a,ll b) {while(b^=a^=b^=a%=b);return a;}
库函数：
__gcd（a,b）

(2)扩展gcd：
求x，y使得gcd(a, b) = a * x + b * y;

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }

    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;

    return d;
}

二：快速幂/快速乘
通过位运算以及将乘法转化为加法 加快乘法的进行以及防止爆数据
mul_mod:a*b mod c快速乘
pow_mode: a^b mod c快速幂

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL mul_mod(LL a,LL b,LL c)   
{
    LL ans=0;
    while(b)
    {
        if(b%2)
            ans=(ans+a)%c;
        a=(a+a)%c;
        b/=2;
    }
    return ans;
}
LL pow_mod(LL a,LL b,LL c)  
{
    LL res=1;
    a=a%c;
    while(b)
    {
        if(b%2)
            res=(res*a)%c;  //res=mul_mod(res,a,c);更快
        a=(a*a)%c;   //a=mul_mod(a,a,c);更快
        b/=2;
    }
    return res;
}

int main()
{
    LL a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    printf("%lld\n",mul_mod(a,b,c));
    printf("%lld\n",pow_mod(a,b,c));
    return 0;
}