社区讨论
一个证明的方法
P3951[NOIP 2017 提高组] 小凯的疑惑参与者 7已保存回复 13
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 13 条
- 当前快照
- 1 份
- 快照标识符
- @mi6mo5rf
- 此快照首次捕获于
- 2025/11/20 07:22 4 个月前
- 此快照最后确认于
- 2025/11/20 07:29 4 个月前
证明当k>ab-a-b时,小凯可以准确支付这个物品。
显然,可以列出一个不定方程ma+nb=k,(m n,为未知数)由于m,n是金币个数,所以m>-1,n>-1,
这个不定方程的通解为m=m0+bt,n=n0-at,(仅仅为写法的一种,不过这样写最方便,m0,n0为方程的一组解),
m0+bt>-1,n0-at>-1,化简后有-(m0+1)/b<t<(n0+1)/a,
显然(n0+1)/a-(-(m0+1)/b)=(n0+1)/a+(m0+1)/b=(bn0+b+a+am0)/ab,
又因为bn0+am0=k.所以原式等于(k+a+b)/ab,显然k+a+b>ab,所以原式大于1,所以区间(-(m0+1)/b,(n0+1)/a,)中必有一个整数,t一定存在,所以命题成立。
又可证明当k=ab-a-b时小凯无法支付(大家可以去参考题解,我就不啰嗦了),
所以ab-a-b就是不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。
(格式有点丑,请见谅)
回复
共 13 条回复,欢迎继续交流。
正在加载回复...