#正題
評測記錄：
https://www.luogu.org/recordnew/show/8283818

---

大意

兩個幣值（互質(zhì)正整數(shù)），求不能完全（需要找零）的最貴的東西。

---

解題思路

首先眾所周知ax+by=c而且a和b互質(zhì)的正整數(shù)，c為正整數(shù)那么x和y一點有整數(shù)解
證明：

證明：因為x0，y0是方程①的整數(shù)解，當(dāng)然滿足ax0+by0=c，②
因此a（x0-bt）+b（y0+at）=ax0+by0=c．
這表明x=x0-bt，y=y0+at也是方程①的解．
設(shè)x′，y′是方程①的任一整數(shù)解，則有
ax′+by′=c．③
③-②得
a（x′-x0）=b′（y0-y′）．④
∵a，b是互質(zhì)的正整數(shù)即（a，b）=1，
∴即y′=y0+at，其中t是整數(shù)．將y′=y0+at代入④，即得x′=x0-bt．
∴x′，y′可以表示成x=x0-bt，y=y0+at的形式，
∴x=x0-bt，y=y0+at表示方程①的一切整數(shù)解．

這道題可以求的就是
$ax+by=max\{k\}(0?x,y)$
所以我們就是要求$x<0ory<0$使$ax+by$最大
那么我們假設(shè)$a>b$
那么$x=?1$時$ax+by$最大
此時$ax?b$，而此時$x$取最大值使整個式子最大
最后最大值是$(b?1)a?b$,因為當(dāng)$x=b$時可以合并同類項變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$(a?1)b$就可以進(jìn)行表示了
然后$(b?1)a?b=ab?a?b$。
然后如果$b>a$推的話是一樣的結(jié)果

---

代碼

#include<cstdio> using namespace std; long long a,b; int main() {scanf("%lld%lld",&a,&b);printf("%lld",a*b-a-b); }

總結(jié)

以上是生活随笔為你收集整理的P3951,jzoj5473-小凯的疑惑【数论】(NOIP2017提高组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。