算法分析
引理：给定$a，b$，若$d = gcd(a,b) > 1$,则一定不能凑出最大数
结论：
如果 $a,b$ 均是正整数且互质，那么由 $ax+by,x≥0,y≥0$ 不能凑出的最大数是 $(a - 1)(b - 1) - 1$。
证明：下面的参考文献
打表找规律方法:（纯摘抄y总的笔记）
#include <iostream>
using namespace std;
//给定一个m，是否能用p和q凑出来
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;
for(int i = 1; i <= 1000;i ++)
{
if(!dfs(i,p,q)) res = i;
}
cout << res << endl;
return 0;
}
时间复杂度 $O(1)$
参考文献
y总的题解
https://www.acwing.com/solution/acwing/content/3165/
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int p = scan.nextInt();
int q = scan.nextInt();
System.out.println((p - 1) * (q - 1) - 1);
}
}
dfs超时了
那是大表代码
不是正解
打表肯定会超的
这个数学原理有学名吗
裴蜀定理
想问一下，为什么不能直接枚举所有组合数插入哈希表中，再从中找出最大的没有插入哈希表中的数返回呢？
兄弟 你和我想的一样 但是不知道上限啊 我是这样理解的
1000太小了，1e5答案对但超时
应该是$gcd(a,b) = 1$
这时候a和b就互质了…
是这样得，当时没有看清楚
引理部分没有错误，本人理解错误了
那我这个呢
互质是什么意思
可以买一下Y总基础课
两个数的最大公约数为1
#include[HTML_REMOVED]
using namespace std;
int main()
{
int x,y;
cin>>x>>y;
cout<<x*y-x-y;
return 0;
}
我觉得这个方法比较简单而且是O(1)
方法都是一样的，主要是找到规律
这个不是普遍规律吧。当x和y的最小公倍数不是两数之积的时候，这个好像不满足吧。（比如4
和6）
有没有可能 题解的公式化简就是这个
为什么打表超时了啊
打表找规律，好像也没有找出(n-1)*(m-1)-1 这个规律 ？ 时间复杂度 为什么是O(1)呢？
找规律这个你可以去看看y总的视频，里面讲得很详细，时间复杂度是O(1)是因为可以直接用公式算出来
看视频没看懂~~
大概的思想是，固定p不变，观察q变化时，答案怎么变化，再固定q不变，观察p变化时，答案怎么变化
请问y总是谁？
大雪菜