继续学习数论…… 本文除非特殊说明，所有的数都是整数 本文参考：欧几里德与扩展欧几里德算法
一、gcd
long long gcd(long long x,long long y){ return y==0?x:gcd(y,x%y); }应该没什么好说的吧……非常朴素的算法 还有一种位运算优化，感觉实现起来非常复杂，NOIP也不大可能卡这个所以就不谈了……
二、lcm 只需要记住一个公式：lcm(x,y)=x*y/gcd(x,y) 随便求→_→
三、EXgcd 那么终于要来到数论2面的道中BossEXgcd 明明是EXgcd为什么不是EX面啊 EXgcd用于解决这样一类问题： 已知(a,b)，求解一组(p,q)，使得pa+qb=gcd(a,b). 解是一定存在的，根据是数论中的某个相关定理。 那么怎么求呢？ pa+qb=gcd(a,b)=gcd(b,a%b)=pb+q(a%b)=pb+q(a- ⌊ a/b ⌋ *b)=qa+(p- ⌊ a/b ⌋ *q)b ∴ p1=q,q2=p−⌊a/b⌋∗q 显然p、q都是单调递减的。而我们在无数次的gcd过程中，b的值最终变成0，即p*a=a，显然此时p=1,q=0是一组解。那么我们有没有办法逆推回去？答案是肯定的。实现：
#include <iostream> using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y){ if(!b){ x=1,y=0; return a; } LL gcd,tmp; gcd=exgcd(b,a%b,x,y); tmp=x; x=y,y=tmp-a/b*y; return gcd; } int main(){ LL a,b,x,y,z; cin>>a>>b; z=exgcd(a,b,x,y); cout<<z<<" "<<x<<" "<<y<<endl; return 0; }四、EXgcd的应用 (一)EXgcd求解不定方程与线性同余方程 定理2.1 对于方程ax+by=c，该方程有整数解的充要条件是c%gcd(a,b)=0 我们可以用扩欧找出 ax0+by0=gcd(a,b) 的一组解。
我们不妨先找出 ax0+by0=gcd(a,b) 的所有解。 定理2.2 方程ax+by=gcd(a,b)的解为
x=x0+bt,y=y0−at，其中t∈Z，x0y0为任意一组整数解 由此可以方便的求出。 从此得到原方程的解： 定理2.3 方程ax+by=c若有整数解，则其整数解为方程ax+by=gcd(a,b)的解乘 cgcd(a,b)如果要求最小正整数解的话： 定理2.4 当t= bgcd(a,b) 时x为最小正整数解，此时x=(x%t+t)%t
而对于线性同模方程 定理2.5 方程ax ≡ c(mod b) ⇔ ax+by=c
好了，定理都说完了，玄学竞赛是不需要证明的，所以我们直接来看一下代码。
#include <iostream> #include <vector> using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y){ if(!b){ x=1,y=0; return a; } LL gcd,tmp; gcd=exgcd(b,a%b,x,y); tmp=x; x=y,y=tmp-a/b*y; return gcd; } vector<pair<LL,LL> > v; bool work(LL a,LL b,LL c,LL l,LL r,LL L,LL R){ LL x,y; LL gcd=exgcd(a,b,x,y); if(c%gcd) return false; x*=c/gcd,y*=c/gcd; v.push_back(make_pair(x,y)); for(LL p=x+b,q=y-a;p<=r&&p>=l&&q<=R&&q>=L;p+=b,q-=a) v.push_back(make_pair(p,q)); for(LL p=x-b,q=y+a;p<=r&&p>=l&&q<=R&&q>=L;p-=b,q+=a) v.push_back(make_pair(p,q)); return true; } int main(){ LL a,b,c,l,r,L,R; cin>>a>>b>>c>>l>>r>>L>>R; if(work(a,b,c,l,r,L,R)){ vector<pair<LL,LL> >::iterator it; for(it=v.begin();it!=v.end();++it) cout<<it->first<<" "<<it->second<<endl; } }（二）exgcd求逆元 逆元是很重要的，逆元是很重要的，逆元是很重要的。 所以掌握逆元的求法是很有必要的事情。 至于逆元怎么用我们之后再提. 逆元的定义：ax ≡ 1(mod b)，且a,b互质则x为a的逆元。 由定义可知，其实我们是在求ax+by=1的解，典型的exgcd应用 那么实现方法：
void exgcd(int a,int b,int c,int &x,int &y){ if(a==0){ x=0,y=c/b; return; }else{ int tx,ty; exgcd(b%a,a,tx,ty); x=ty-(b/a)*tx; y=tx; return; } }那么相关的例题我们之后和逆元一起说吧，因为逆元大概凑不够字数orz
