Go语言视频零基础入门到精通

admin

day1

---

1、小凯的疑惑
【题目描述】
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。
【输入格式】
输入数据仅一行，包含两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯手中金币的面值。
【输出格式】
输出文件仅一行，一个正整数 N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。
【样例输入】
3 7
【样例输出】
11
【数据规模】

【分析】
简化题意，就是当正整数a,b互质时，不能用a,b表示出的最大数是多少（把这句话放百度上搜下就有答案了）。
结论很简单：
   
    a∗b−a−b
   a*b-a-b。这个结论看看给的2个样例就能推个大概了，然后写个循环的暴力程序算算，应该还是不难推出的（小学奥数都不会推结论还考啥提高组嘛）。
下面给出证明（摘自http://blog.sina.com.cn/s/blog_4a6685e9010007wj.html）：
首先互质的两数的最小公倍数是a*b。设
   
    f(n)
   f(n)表示使
   
    f(n)∗b
   f(n)*b%
   
    a=n
   a=n成立的最小正整数（
   
    1≤n<a
   1≤n），则
   
    0<f(n)<a
   0。显然
   
    f(n)
   f(n)一定不是
   
    a
   a的倍数，且
   
    f(1)
   f(1)~
   
    f(n)
   f(n)各不相同。
取一个大于
   
    a∗b
   a*b的数
   
    x
   x，可以这么写：
   
    x=a∗b+m∗a+n
   x=a*b+m*a+n，这里m是变量，
   
    n=x
   n=x%
   
    a
   a。