# 扩展欧几里得、gcd、快速幂模板

# 一、gcd 模板

gcd 全称就是最大公约数，lcm 是最小公倍数，而 lcm 可以很容易根据 gcd 得出，所以这里只给出 gcd 的代码

Code:

typedef long long ll;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

# 二、扩展欧几里得

先简单介绍一下其作用：

1、求解不定方程

2、求解模的逆元

3、求解线性同余方程

例题：有理数取余

Code:

#include <bits/stdc++.h>
using namespace std;
const int mod=19260817;
const int N=10001;
typedef long long ll;
int a[N],b[N];
ll expand(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll r=expand(b,a%b,x,y);
    ll t=y;
    y=x-(a/b)*y;
    x=t;
    return r;
}
int main()
{
	char ch[N];
	scanf("%s",ch);
	int len=strlen(ch);
	ll aa=0,bb=0;
	for(int i=0;i<len;i++)
		aa=(aa*10+ch[i]-'0')%mod;
	scanf("%s",ch);
	len=strlen(ch);
	for(int i=0;i<len;i++)
		bb=(bb*10+ch[i]-'0')%mod;
	ll x0,y0;
	expand(bb,mod,x0,y0);
	if(bb==0)
		printf("Angry!\n");
	else
		printf("%lld\n",(aa*((x0%mod+mod)%mod))%mod);
	return 0;
}

原理方面请移步另一篇文章

# 三、快速幂

正常的求$x^n$ 需要$O(n)$ 的时间复杂度，快速幂就是把$O(n)$ 时间复杂度缩减为$O(logn)$ 的算法，本质上运用了分治的思想

Code:

typedef long long ll;
ll mod; 
ll quickpow(ll x,ll zs)
{
    ll ans=0;
    while(zs)
    {
        if(zs&1)
        {
            ans=ans*x%mod;
            ans%=mod;
        }
        x*=x;
        x%=mod;
        zs/=2;
    }
    return ans%mod;
}