acwing1205. 买不到的数目

题目

题解

• dp做法
  关于不会大于n*m的证明：
  猜测这个不能由n,m凑出来的数应该是不会超过nm,至于证明，我是这样想的,反证法
  假设不能被凑出的最大的数大于 n·m 即:x - n · m > 0
  说明不存在任何一对a,b和d使得以下式子成立(由于x不能被凑出来所以加上一个d): x = a·n + b·m + d
  代入上式计算得到：a·n + b·m + d - m·n > 0即此式不成立,我们可以取a = m,b = n上式变为 m·n + d > 0 可以发现这是必成立的(抛去0)与假设矛盾，所以x一定不大于nm

#include<iostream>
using namespace std;
const int N=1000000;
bool f[N];
int n,m,ans;
int main(){
    cin>>n>>m;
    f[0]=true;
    int minx=min(n,m);
    int maxx=max(n,m);
    for(int i=minx;i<=n*m;i++){
        if(f[i-minx]){
            f[i]=true;
        }else if(i>=maxx&&f[i-maxx]){
            f[i]=true;
        }else {
            ans=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

• 数论做法

打表找规律。

#include<iostream>
using namespace std;
int n,m;
int main(){
    cin>>n>>m;
    cout<<(n-1)*(m-1)-1<<endl;
    
    return 0;
}