UVA 10090 扩展欧几里得算法

UVA 10090 扩展欧几里得算法,第1张

概述题目连接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=1031&mosmsg=Submission+received+with+ID+8778298   这道题的数据规模达到了惊人的2*10^9,所以得用long才能装得下而且只要

题目连接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=1031&mosmsg=Submission+received+with+ID+8778298

这道题的数据规模达到了惊人的2*10^9,所以得用long才能装得下而且只要有一丝的暴力思想就会TLE

仔细观察题目可以发现如果每一个盒子都要装满的话,则必须满足以下条件:

am1+bm2=n

这个式子很像那个扩展欧几里得里面的那个,于是很容易联想到

ax+by=gcd(a,b)=g

根绝这个方程的特点,可以判断,如果n%gcd(a,b)!=0的话,则无解(参见《数论概论》)

于是联立这两个方程我们可以解出m1,m2

解出来m1=nx/g m2=ny/g

那么通解则应该是m1=nx/g+bt/g m2=ny/g-at/g(注意这里不能直接用ax+by=g的最小解来计算m1和m2,另外t是一个整数)

由题目的意思,可以判断m1和m2不可能为负数

于是m1>=0,m2>=0

这样我们可以解出t的范围:-nx/b<=t<=ny/a 这里的t必须是整数

我们假定:

t1=ceil(-nx/b)

t2=floor(ny/b)

如果t1>t2的话则t就没有一个可行的解,于是肯定也是无解的情况,所以输出不可能的两种情况就明确了

接下来,我们再来计算最终的价格V

V=va*m1+vb*m2

带入m1和m2的表达式可以得到

V=va*(xn/g+bt/g)+vb*(yn/g-at/g)

=((b*va-a*vb)/g)*t+(va*xn+vb*yn)/g

这个很明显是关于t的一个一次函数(出了t意外的数都是常数)

于是V(t)的单调性由(b*va-a*vb)来确定

所以当b*va-a*vb>=0的时候,t就要取最小才能让V(t)最小

反之,则t要去取最大才行

这里t的范围(定义域)已经是确定了的,所以t只有可能有两个取值

就是t1或者t2

剩下的问题就很明确了,得到t之后,再把t的值带入m1 m2的式子里面就可以计算出答案了

我的代码:

总结

以上是内存溢出为你收集整理的UVA 10090 扩展欧几里得算法全部内容,希望文章能够帮你解决UVA 10090 扩展欧几里得算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1293163.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存