title: 简单数学问题的python实现 date: 2020-03-27 22:13:26 categories: 算法 tags: [python, 简单数学]
小明开了一家糖果店。
他别出心裁：把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
两个正整数 n,mn,m，表示每种包装中糖的颗数。
一个正整数，表示最大不能买到的糖数。
2≤n,m≤10002≤n,m≤1000， 保证数据一定有解。
裴蜀定理（或贝祖定理）
若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.（数论）O（1） 结论： 如果a，b均是正整数且互质，那么由ax+by，x≥0，y>0不能凑出的最大数是ab-a-b。 证明：https://www.cnblogs.com/Yuzao/p/7074465.html
暴力打表
IA=lambda: map(int,input().split()) n,m=IA() flag=0 def dfs(i,a,b): if i==0:return 1 if i>=a and dfs(i-a,a,b)==1: return 1 if i>=b and dfs(i-b,a,b)==1: return 1 return 0 for i in range(100,0,-1): flag=0 if dfs(i,n,m)==0: print(i) break IA=lambda: map(int,input().split()) n,m=IA() print(n*m-n-m)