### 技术控

今日:415| 主题:53513

# [其他] Find the minimum value of m that satisfies ax + by = m and all values after m al

131 0

### 立即注册CoLaBug.com会员，免费获得投稿人的专业资料，享用更多功能，玩转个人品牌！

x
Given two positive integers ‘a’ and ‘b’ that represent coefficients in equation ax + by = m. Find the minimum value of m that satisfies the equation for any positive integer values of x and y. And after this minimum value, the equation is satisfied by all (greater) values of m. If no such minimum value exists, return “-1”.
Examples:
1. Input: a = 4, b = 7
2. Output: 18
3. Explanation: 18 is the smallest value that can
4.              can be satisfied by equation 4x + 7y.
5.              4*1 + 7*2 = 18

6.              And after 18 all values are satisifed
7.              4*3 + 7*1 = 19
8.              4*5 + 7*0 = 20
9.              ... and so on.

This is a variation of    Frobenius coin problem. In Frobenius coin problem, we need to find the largest number that can not be represented using two coins. The largest amount for coins with denominations as ‘a’ and ‘b’ is a*b – (a+b).
This question is a direct implementation of a theorem – “Chicken McNugget Theorem”. It states that if the two numbers, a and b, are co-prime, then there exists an minimum integer m, above which ax + by = m is true for any positive numbers x and y.
1. // C++ program to find the minimum value of m that satisfies
2. // ax + by = m and all values after m also satisfy
3. #include<bits/stdc++.h>
4. using namespace std;

5. int findMin(int a, int b)
6. {
7.     // If GCD is not 1, then there is no such value,
8.     // else value is obtained using "a*b-a-b+1'
9.     return (__gcd(a, b) == 1)? a*b-a-b+1 : -1;
10. }

11. // Driver code
12. int main()
13. {
14.     int a = 4, b = 7;
15.     cout << findMin(a, b) << endl;
16.     return 0;
17. }

Output:
This article is contributed by    Rishabh Jain. If you like GeeksforGeeks and would like to contribute, you can also write an article using    contribute.geeksforgeeks.orgor mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.

• ## Twitter considering subscription model a

In the latest segment of Twitter’s journey t [...]

• ## 我还在原地等你，你却假装忘记曾来过这里…

【美图心语】青春如酒，成长正酣，所有美好的， [...]

• ## 众筹新规5月份或将出台：终结野蛮生长

日前有消息称，5月份或将出台股权众筹的指导意 [...]

• ## “关店魔咒”下的自我救赎：1年关了185家店

来源：投资界(微信公众号ID：PEdaily2012) 作者 [...]

• ## Crunch Report | Amazon Buys Souq

Today’s Stories [*] Amazon to ac [...]

• ## Amazon to acquire Souq, a Middle East cl

Amazon continues its march across the glob [...]

• ## 上海单车标准出台，能解决共享单车使用乱象

摘要： 善战者，因其势而利导之，或许共享单车 [...]

• ## Uber CEO卡拉尼克：实现员工多元化当前首要

据《今日美国报》北京时间3月25日报道，Uber CEO [...]

• ## 总经理离职，儿子创业，曹德旺的接班人在哪

近日，福耀玻璃（600660.SH）发布一则公告，外界 [...]

• ## 周鸿祎："好领导者"的四个关键词

最近我和一批年轻的创业者去看了《鸣梁海战》， [...]

© 2001-2017 Comsenz Inc. Design: Dean. DiscuzFans.