题目描述

小明开了一家糖果店。
他别出心裁：把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式
两个正整数
n,m
n,m
，表示每种包装中糖的颗数。
输出格式
一个正整数，表示最大不能买到的糖数。
数据范围
2≤n,m≤1000
2≤n,m≤1000
，
保证数据一定有解。

样例

输入样例：
4 7
输出样例：
17

算法1

(裴蜀定理) $O(1)$

裴蜀公式:p*q-p-q
若a,ba,b a,ba,b是整数,且gcd(a,b)=dgcd(a,b)=d gcd(a,b)=dgcd(a,b)=d，那么对于任意的整数x,y,ax+byx,y,ax+by x,y,ax+byx,y,ax+by都一定是dd dd的倍数，特别地，一定存在整数x,yx,y x,yx,y，使ax+by=dax+by=d ax+by=dax+by=d成立。 ——引自百度百科

B站李永乐讲解裴蜀定理:https://www.bilibili.com/video/av77974575?from=search&seid=11843861101841113707

C++ 代码

#include<iostream>
using namespace std;

int main(){
    int p,q;
    cin>>p>>q;
    cout<<p*q-p-q<<endl;
    return 0;
}

算法2

(暴力枚举) $O(n!)$ //瞎猜的

虽然会超时,但可以过一半样例

时间复杂度

C++ 代码

#include<iostream>
using namespace std;

bool dfs(int k,int p,int q){
    if(k==0)
    return true;
    if(k>=p&&dfs(k-p,p,q))return true;
    if(k>=q&&dfs(k-q,p,q))return true;

    return false;
}

int main(){
    int p,q;
    cin>>p>>q;
   int res = 0;
   for(int i = 1 ; i <=1000 ; i++)
   {
       if(!dfs(i,p,q))res = i;
   }

   cout<<res<<endl;

   return 0;
}