蒟蒻求助使用非负大整数类求求两个非负整数的最大公约数数的问题

来源：蜘蛛抓取(WebSpider) 时间：2016-06-12 10:39 标签： 求两个非负整数的最大公约数

        今天看了一个辗除法求求两个非負整数的最大公约数数的例子上网查了一下其数学原理，算是理解了这个算法的数学依据

参考有关资料上的编程实例，编写的C语言程序如下：

        今天在编译运行的时候出了点差错输入两个数后得到的结果不正确，得到的是比较奇怪的数我就把两个正整数不用输入改为洎己赋初值，此时得到的结果正确由此可见应该是输入的时候出错了。经过检查发现scanf("%d,%d",&num1, &num2); 这句输入程序中两个%d之间有逗号而我从键盘输入時没有输这个逗号，导致了出错要么把逗号去除，要么输数的时候两数之间加个逗号就正确了这个错误可以给初学编程的人作为参考，避免犯类似的低级错误

版权声明：本文为博主原创文章未经博主允许不得转载。 /lxc/article/details/

在写斜率优化之前我们来回顾一下单调队列优化的dp
1. 对于如下形式的dp方程

2.对于如下形式的dp方程

我們可以用一个单调队列维护一个(i - m, j)中dp[j] + f(j)的最小值，然后做到O(1)转移

的方程，无法做到O(1)计算

的最小值这时就需要斜率优化这個技巧来解决这个问题了。


我们就能通过斜率优化这个dp了



从j转移到i, 比从k转移到i更优，变换此不等式可得:


则将此不等式化解为上述形式

所以这种情况时，我们可以直接把j点删除最后能够转移的点集只会存在这种图形，
所以最后我们维护一个上凸集即可
但是此時我们还是没有解决最终问题，如何才能找到转移到i点的最优的点呢可以发现最后的点集一定是一个凸集，也就是斜率单调！！这样对於k < j, grad(j,k) < f(i),时更优从图形特点我们可以发现如果j比k优，那么j点比所有比k小的点都优所以对于每一个f(i),我们维护一个所有比i点小的凸集，二分查找斜率比f(i)小的编号最大的点就是最优的转移点。如果f(i)也满足单调性比如这道题，我们还可以直接维护一个单调队列就能解决这个问题

对于f(i)单调的这种情况，除了使用单调队列优化的斜率优化做我们还有另外一种分治的做法，但是复杂度会变成O(nlogn) 比O(n)差
当f(i)单调的時候，我们可以发现若a > b,则f(a) > f(b),设转移到a的最优点是c转移到b的最优点是d，一定有c > d也就是转移到a的最优点一定大于等于转移到b的最优点。考虑這样的分治

可以发现这个分治比起斜率优化不仅写起来方便很多，并且适用的范围也更广这个做法不局限于斜率单调，可以发现只要滿足c是更新f(a)的最优点d是更新f(b)的最优点，若a > b 一定有 c > d则可以有这个分治做。

这个做法是我在,跟Claris神犇的代码学会的,在此特地感谢Claris.这个做法着實是非常的劲啊！多一个log但是换来编码复杂度和通用性更广的解法。

我要回帖

更多关于 求两个非负整数的最大公约数 的文章

 

随机推荐