1205. 买不到的数目

[maninbule]

1205. 买不到的数目

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式

两个正整数 n,m，表示每种包装中糖的颗数。

输出格式

一个正整数，表示最大不能买到的糖数。

数据范围

2≤n,m≤1000，

保证数据一定有解。

输入样例：

4 7

输出样例：

17

[maninbule]

当a与b不互质的时候，一定无解，也就是没有最大不能表达的数

d = gcd(a,b)>1时，y = ax+by = kd 一定是d的倍数, 那么所有不是d的倍数的数，ax+by是不能组合出来的

当a与b互质的时候

根据裴蜀定理，一定存在整数解x,y使得ax+by = 1,注意只是整数！

那么要让x，y为非负整数怎么做

ax+by = 1

amx+bmy) = m （我们的目标值是m）

(xm-b)a +(ym+a)b = m

然后将x，y重新定义成x = xm-b,y = ym+a

所以只要xm-b,ym+a，大于等于0，就有非负整数解

所以是有限制

一定有个界限，界限之后一定有解，所以可以进行暴力求解找找规律

找规律代码:

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
typedef pair<int,int> pii;

int N,M;
int st[maxn];
int main(){
    cin>>N>>M;
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    for(int i = 0;i<1000;i++){
        for(int j = 0;j<1000;j++){
            if(N*i+M*j<1e6){
                st[N*i+M*j] = 1;
            }
        }
    }
    for(int i = 1;i<1000;i++){
        if(st[i] == 0 ){
            printf("%d\n",i);
        }
    }

    return 0;
}

4 7 ->17;
5 8 ->27;
11 10->89;

规律得：x = a*b-a-b

AC

#include <iostream>
using namespace std;

int n,m;
int main(){
    cin>>n>>m;
    cout<<n*m-n-m<<endl;

    return 0;
}

[xunzhang123]

//数学公式 (p - 1) * (q - 1) - 1

include

using namespace std; int main() { int p, q; cin >> p >> q; cout << (p - 1) * (q - 1) - 1 << endl; return 0; }

[LJM-Jeson]

include

using namespace std; int main() { int a, b; cin >> a >> b; cout << a * b - a - b << endl; return 0; }

[maobohui]

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    cout<<n*m-n-m<<endl;
    return 0;
}