算法
(数论) O(1)
结论:
如果 a,b 均是正整数且互质,那么由 ax+by,x≥0,y≥0 不能凑出的最大数是 ab−a−b。
下面给出证明:
首先证明 ab−a−b 不能被 ax+bx,x≥0,y≥0表示出。
反证法,假设 ab−a−b=ax+by,那么 ab=a(x+1)+b(y+1),由于 a|ab,a|a(x+1),所以 a|b(y+1),由于 a,b 互质,所以 a|(y+1),由于 y≥0,所以 a<=y+1,所以 b(y+1)≥ab。同理可得 a(x+1)≥ab,所以 a(x+1)+b(y+1)≥2ab>ab,矛盾。
证明 ab−a−b+d,d>0 一定可以表示成 ax+by,x,y≥0 的形式,可以参考这篇博客。
时间复杂度分析
计算 ab−a−b 的时间复杂度是 O(1)。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
LL a, b;
cin >> a >> b;
cout << a * b - a - b << endl;
return 0;
}
666
若 gcd(a,b)=d>1 怎么做?
这种情况没解,不会出现的
互质才有这个结论
不互质,就不知道了
参考的博客,最后的推出有问题。应该是 (p−1+B)q+(A−1)p+k∗min(p,q)
然后 因为 k>=0,(p−1+B)>=0,(A−1)>=0,所以得证
反证法上面一行,ax+by
对
反证法,写错字了
多谢指正,已修正。