欧几里德算法：欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数(Thegreatestcommondivisor)。其计算原理依赖于下面的定理：定理：gcd(a,b)=gcd(b,amodb)(a>b且amodb不为0)证明：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则...

拓展欧几里得公式： typedeflonglongLL;LLexgcd(LLa,LLb,LL&x,LL&y){if(a==0&&b==0)return-1;if(b==0){x=1;y=0;returna;}LLd=exgcd(b,a%b,y,x);y-=a/b*x;retur...

转载自：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,...

欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。第一种证明：   a可以表示成a=kb+r，则r=amodb　　假设d是a,b的...

　　两只青蛙，现在分别在x,y的位置，以m,n的速度在周长为L的环形跑道上面跑。　　问他们什么时候可以到同一个位置。（如果永远不能，则输出Impossible）　　扩展欧几里德模板题。　　设a=x-y,b=n-m,　　我们可以列出方程：ax ≡b(modL)   &n...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ42.html首先我们把式子改写一下：$$(-1)^{lfloorafloor}\=1-2(lfloorafloormod2)\=1-2(lfloorafloor-2lfloorfraca2floor)$$于是问题就变成了求解...

原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-H.html　　有两只蚂蚁在一个二维平面上走。一开始，他们都在点$(1,0)$的位置。　　Rikka布置了三条规定：　　1.　第一只蚂蚁不能走过直线$y=cfrac{a}{b}...

原文链接https://www.cnblogs.com/zhouzhendong/p/NOI2018Day2T1.html 　　首先我们仔细看一看样例可以发现如果一回合打不过巨龙就输了。　　所以每一回合都要赢。所以每一次选择的宝剑都是可以提前预知的。　　我们用个set来支持快速插入和upper_bound，可...

原文链接http://www.cnblogs.com/zhouzhendong/p/9055728.html 　　一束与坐标轴平行或者成$45^circ$角的光线在一个矩形区域内反射。　　如图：　　　　给定矩形的长宽，以及光源位置、光线初始方向，问它最先到达四个角落中的哪一个角落。如果永远不能到达，输出$-1...

　　给出k个同余方程组：xmodai=ri。求x的最小正值。如果不存在这样的x，那么输出-1.不满足所有的ai互质。　　UPD(2018-08-07):　　本题做法为扩展中国剩余定理。　　我写了一篇证明：链接：https://www.cnblogs.com/zhouzhendong/p/exCRT.html　　代码就不...

　　对于C的for(i=A;i!=B;i+=C)循环语句，问在k位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数。否则输出死循环。　　原题题意再次缩略：　　求x的最小正整数值。　　我们把式子稍微变一下形：　　然后就变成了一个基础的二元一次方程求解，扩展欧几里德套套就可以了。　　至于扩展欧几里德（ex_gc...