1. 从跳兽问题
问题描述:
有一只跳兽,每次跳的步数为m,在一个长为n的道路上来回跳。当接近一个端点,且余下的距离又不足一步时,先跳到该端点,再折回,其折回的距离是刚才未跳完的长度。跳兽从一端跳出,问能不能到达距离该端点1米的地方。
分析:
我们不妨将n的道路按照另一个端点对称一下,并且一直延伸下去
得到如下所示的一个道路:
可以发现:夹子的位置是2yn±1。而跳兽每次跳到的位置是mx
所以就得到一个方程式:mx+2ny=1
这样我们就可以用扩展欧几里德算法来判断有没有解:即gcd(2n,m)=1便能到达,否则无法到达。
2.Magic Horse
问题描述:
在一个相当大的棋盘上,有一只Magic Horse,每次能跳一个a×b大小的位置,问这只Magic Horse能走遍整个棋盘吗?
分析:
由于是无穷大的棋盘,肯定是不能用枚举法来做的。如果能够跳到旁边的格子,必然能够跳到所有的位置。
可以发现:从(0,0)出发,可以到以下八个位置:
(a,b) (a,-b) (-a,b) (-a,-b) (b,a) (b,-a) (-b,a) (-b,-a)
所以经过若干次跳动之后,所能到达的位置一定是:
dx=p1a+q1b
dy=p2a+q2b
所以只需要gcd(a,b)=1即可。
但是这只是一个条件,还有一个隐含条件。
从起点跳到相邻的一点,坐标之和的奇偶性一定发生了变化。如果a和b的奇偶性相同,那么不论怎么跳,坐标之后的奇偶性不会发生改变。所以a和b的奇偶性不同。
3. 邮票问题
问题描述:
给你两种面额的邮票A,B。问能否用A、B组成所有大于0的不同面额。如果可以,输出0。如果不能,输出有几种面额无法组合而得,如果无法组成的情况有无穷多种,输出"infinite"。
分析:
首先可以列出Ax+By=1的方程,如果gcd(A,B)!=1。那么对于1,1+A×B,1+2×A×B,……都无法表示为A,B的组合。
如果gcd(A,B)=1,那么又有多少种是无法组成的呢。
首先可以证明所有大于A×B的都可以表示出来。(证明比较复杂,有兴趣的可以参阅《ACM/ICPC程序设计与分析》,(沈云付))
其次是求出小于A×B的这些数当中,那些是不可以表示为A,B的组合的
可以用枚举法,一一枚举。这里给出一个公式 S=(A-1)×(B-1)/2 (证明过程略)
分享到:
相关推荐
欧几里德算法和扩展欧几里德算法,经典算法系列
欧几里德算法和扩展欧几里德算法.doc
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
扩展欧几里德算法 欧几里德算法 代码 不可多得的资源
实现扩展欧几里得算法的代码,很简单,能够成功运行。
欧几里德算法和扩展欧几里德算法。用C和C++实现。.zip
就是扩展欧几里德算法
acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 很详细的讲解哦!
RSA扩展欧几里德算法算例,说明RSA密钥计算过程.
欧几里德算法 欧几里德算法 欧几里德算法 欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们 很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为 止。可是它们出发之前忘记了一件很...求出它们跳了几次以后才会碰面。
扩展欧几里得算法求逆元
Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
个人初学C++,小试身手,供参考,网上有很多,我的是原创,但不是最好的
欧几里德算法和扩展.doc
包含两个功能。 one 函数计算两个多项式 a(x) 和 b(x) 在 GF(2^m) 上... 另一个函数执行扩展的欧几里德算法,其中除了 a(x) 和 b(x) 的 gcd 之外,还计算了两个多项式 u(x) 和 v(x),使得 gcd = u(x)a(x) + v(x)b(x)。
欧几里德C语言算法
适合初学者适合初学者 欧几里德算法 适合初学者适合初学者 欧几里德算法 适合初学者适合初学者 欧几里德算法
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
欧几里德算法