题目描述

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。

输入输出格式

输入格式：

输入数据仅一行，包含两个正整数 aa 和 bb，它们之间用一个空格隔开，表示小凯手中金币的面值。

输出格式：

输出文件仅一行，一个正整数 NN，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。

【数据范围与约定】

对于 30%的数据： 1 \le a,b \le 501≤a,b≤50。

对于 60%的数据： 1 \le a,b \le 10^41≤a,b≤104。

对于 100%的数据：1 \le a,b \le 10^91≤a,b≤109。

【题解】

①可以得到结论：ans=a*b-a-b（然后你可以水掉它或者继续到②）

②

引理：不定方程：ax+by=c若有解，a，b，c＞0

则必有一特解使得-a＜y0≤0，x＞0；

（引理可以用数轴法，不再赘述）

证明：

先证ax+by=ab-a-b在题设下无解

-》 a（x+1）+b（y+1）=ab 可得：a|y+1 b|x+1 ，

于是可设：y=k2*a-1，x=k1*b-1 k1，k2＞0；

-》 ab*（k1+k2-1）=0 即（k1+k2-1）=0矛盾；

再证ax+by=ab-a-b+k（k＞0）在题设下必有解

-》 a（x+1）+b（y+1）=ab+k 设x+1=x1，y+1=y1 不失正确性的将它拆成：

ax1+by1=ab …① ax2+by2=k …②

由①可得x1=0，y1=a的特解，由②再加引理可得有一组x2＞0，-a＜ y2≤0 加一加就可以得到原方程必有一组解使得x＞0，0＜y≤a；

综上即ab-a-b为ans

证毕。

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define Run(i,l,r) for(int i=l;i<=r;i++)

 #define Don(i,l,r) for(int i=l;i>=r;i--)

 using namespace std;

 ll a,b;

 int main()

 {    cin>>a>>b;

     cout<<a*b-a-b<<endl;

     return ;

 }//by tkys_Austin;

巴特西

【NOIP2017 D1 T1 小凯的疑惑】

题目描述

输入输出格式

（引理可以用数轴法，不再赘述）

证明：

最新文章

热门文章