AcWing 1205. 买不到的数目 （数学知识）

前提条件：给定a，b，若d=gcd(a,b)>1,则一定不能凑出最大数

因为若d>1，则a和b一定是d的倍数，那么a和b凑出来的数也肯定是d的倍数，所以一定不会存在一个最大数，使得这个数之后的数字都能被a和b凑出来

结论： 如果 a,b均是正整数且互质，那么由 ax+by,x≥0,y≥0不能凑出的最大数是 (a−1)(b−1)−1。

互质：最大公约数为1

裴蜀定理：若a,b的最大公约数为d，怎一定存在两个整数p,q使得ap+bq=d，只要ab互质，则一定有解

若ab互质，则一定存在ap+bq=1，两边同时乘以m  =>  apm+bqm=m  =>  （am-q)p+(bm+p)q=m

1. 暴力搜索（打表）

会超时，但是主要学习暴搜函数的写法

• 当要凑的数字减到0的时候，说明凑出来了
• 先尝试用p来凑，要凑的数字变成m-p
• 再尝试用q来凑，要凑的数字变成m-q
• 如果都凑不出来，则返回false

注意：递归不是只执行其中一个if分支，而是执行完了一个后如果不行，会在返回的时候继续执行下一个

#include<bits/stdc++.h>
using namespace std;

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

int main(){
    int p,q;
    cin>>p>>q;
    int res=0;
    int t=min(p,q);
    for(int i=t;i<2000;i++){
        if(i%p==0) continue;
        else if(i%q==0) continue;
        else if(!dfs(i,p,q)) res=i;
    }
    cout<<res<<endl;
    return 0;
}

2. 公式：（p-1)(q-1)-1

#include<bits/stdc++.h>
using namespace std;

int main(){
    int p,q;
    cin>>p>>q;
    int res=0;
    int t=min(p,q);
    res=(p-1)*(q-1)-1;
    cout<<res<<endl;
    return 0;
}