NOIP2017提高组 luogu3951 小凯的疑惑

NOIP2017提高组 luogu3951 小凯的疑惑

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

输入输出格式 输入格式：

输入数据仅一行，包含两个正整数

a

a 和

b

b，它们之间用一个空格隔开，表示小凯手 中金币的面值。

输出格式：

输出文件仅一行，一个正整数

N

N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。

输入输出样例 输入样例#1： 复制

3 7 输出样例#1： 复制

11 说明 【输入输出样例 1 说明】

小凯手中有面值为3和7的金币无数个，在不找零的前提下无法准确支付价值为1、 2、4、5、8、11 的物品，其中最贵的物品价值为 11，比 11 贵的物品都能买到，比如：

12 = 3 \times 4 + 7 \times 0

12=3×4+7×0

13 = 3 \times 2 + 7 \times 1

13=3×2+7×1

14 = 3 \times 0 + 7 \times 2

14=3×0+7×2

15 = 3 \times 5 + 7 \times 0

15=3×5+7×0

【数据范围与约定】

对于 30%的数据：

1 \le a,b \le 50

1≤a,b≤50。

对于 60%的数据：

1 \le a,b \le 10^4

1≤a,b≤104。

对于 100%的数据：

1 \le a,b \le 10^9

1≤a,b≤109。

说明 这个做法是我在考场上想出来的 ex_gcd 做法，当时并没有想到打表，所以向发表一下让大家彻底摆脱小学奥数带来的阴影，我现在仍然认为，ex_gcd 是这道题的标算。

题解 首先，我们发现这两个数是互质的，并且有无限个。很容易想到不定方程

ax + by = gcd(a, b) ax+by=gcd(a,b) ，其中

gcd(a, b) = 1 gcd(a,b)=1 。

然后我们考虑，对于所有可行的能被

a a 和

b b 表示出来的数

k k ，都存在

x \geq 0, y \geq 0,ax + by = k x≥0,y≥0,ax+by=k。

现在我们要构造的是最大的不合法的数，显然，这个数

1+1 一定是一个合法的数，转化成了求最大的减一后不合法的数。

由于这个数

k k 一定是合法的，所以满足性质

\exists x \geq 0, \exists y \geq 0,ax + by = k ∃x≥0,∃y≥0,ax+by=k

那么如果

k-1 k−1 合法，那么

k - 1 k−1 可以表示成

a \left ( x - x’ \right ) + b \left ( y - y’ \right ) = k a(x−x′)+b(y−y′)=k

或

a \left ( x - x” \right ) + b \left ( y - y” \right ) = k a(x−x′′)+b(y−y′′)=k

其中

x’,y’ x′,y′ 表示

ax + by = 1 ax+by=1 的

x x 最小且非负的整数解;

x”,y” x′′,y′′ 表示

ax + by = 1 ax+by=1 的

y y 最小且非负的整数解。

那么现在只需要让

x - x’< 0 x−x′<0 并且

y - y” < 0 y−y′′<0 即可

那么最后的最大的减一后不合法的数就是

a \left ( x’ - 1 \right ) + b \left ( y” - 1 \right ) a(x′−1)+b(y′′−1)

那么最后的答案就是

a \left ( x’ - 1 \right ) + b \left ( y” - 1 \right ) - 1 a(x′−1)+b(y′′−1)−1

证明： 首先充分性成立。

然后证明必要性：若

a \left ( x’ - 1 \right ) + b \left ( y” - 1 \right ) a(x′−1)+b(y′′−1)不是最大的减一后不合法的数，那么一定存在一个更大的数，显然该数的

a a 的系数大于

x’ - 1 x′−1 或

b b 的系数大于

y” - 1 y′′−1 （如果都小于等于，那么该数不会比当前数大）。显然，减一后仍然是合法的。所以必要性成立。

综上，

a(x′−1)+b(y″−1)−1 a ( x ′ − 1 ) + b ( y ″ − 1 ) − 1 a(x′−1)+b(y′′−1)−1 是最大的不合法的数。

#includeint a,b;int main(){ // freopen("math.in","r",stdin); //freopen("math.out","w",stdout); scanf("%d%d",&a,&b); long long ans=(long long)a*b-a-b; printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。