题目连接: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的式子里面就可以计算出答案了
我的代码:
分享到:
相关推荐
扩展欧几里得算法求逆元
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
欧几里德算法和扩展欧几里德算法,经典算法系列
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
扩展欧几里德算法 欧几里德算法 代码 不可多得的资源
matlab的M函数文件,附带了函数的使用说明了
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
本算法实现了用扩展欧几里得的方法求最大公因子和模逆元的方法,可以直接运行。
信息安全入门基本必备,将基础的欧几里得扩展所得的扩展欧几里得算法。
欧几里德算法和扩展欧几里德算法.doc
实现扩展欧几里得算法的代码,很简单,能够成功运行。
RSA扩展欧几里德算法算例,说明RSA密钥计算过程.
包括完整的c语言实现扩展的欧几里得算法代码截图和相关代码说明以及程序截图
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
欧几里德算法和扩展欧几里德算法。用C和C++实现。.zip
35扩展欧几里得算法1
介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 很详细的讲解哦!
就是扩展欧几里德算法