1 设p q的最大公约数为d (d>1)
则不是
d的倍数的全都出不来——不存在最大出不来的数
2 若d==1 (p,q)互质
(不太理解和这道题的关系)
裴蜀定理
若p q 的最大公约数是d
则:一定存在整数a,b
使得ap+bq=d
则:
若pq互质 一定存在ap+bq=1
则取数M 时 只需让左右两边同时*M
则任何数M必然能够被取到
即一定有解
打表找规律
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool dfs(int i,int p,int q){
if(i==0) return true;
if(i>=p&&dfs(i-p,p,q)) return true;
if(i>=q&&dfs(i-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;
}
超时 过了6/11个数据
得出结论:
p q互质时 不能被p和q凑出来的最大整数:
(p-1)(q-1)-1
最终代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int p,q;
cin>>p>>q;
cout<<(p-1)*(q-1)-1<<endl;
return 0;
}