数论+DP

定理： 若gcd(p,q)=1,则任意大于pq-p-q的数都能被p,q表示。

证明：

• 1.pq−p−q不能用px+qy表示
  设px+qy=pq−p−q,其中:x≥0y≥0(很重要！！！)
  则:p(x+1)+q(y+1)=pq
  所以p|y+1,q|x+1
  因为p(x+1)≤pq,q(y+1)≤pq
  设:x+1=kq
  代入得:kpq+q(y+1)=pq
  整理得:y+1=(1−k)p
  又因为:k>0且x≥0,y≥0
  所以:pq−p−q不能用px+qy表示

• 2.对于n>pq−q−p,都可以表示成px+qy
  设n>pq−p−q
  则(p−1)(q−1)=pq−p−q+1
  所以n≥(p−1)(q−1)
  因为gcd(p,q)=1
  则对于z[HTML_REMOVED]0>b
  显然a>0
  若a>q:
  设a1=a−q,b1=b+p
  则有a1p+b1q=z
  若a1>q:
  则可得到：a2p+b2q=z且0<|a2|[HTML_REMOVED]0
  则n=pq−q−p+k×min(p,q)+r=(q−1)p−p+k×min(p,q)+Ap+Bq=(A−1)p+(B+q−1)p+k×min(p,q)
  其中(A−1),(B+q−1)≥0
  则无论min(p,q)是p还是q，都有n=pq−p−q+k×min(p,q)+r
  所以对于n>pq−q−p,都可以表示成px+qy

由上面的证明可知：

• 题意：
  若每种包装盒装的个数不能够互质，所不能装的就没有上限，所以输出0
  若能满足上一条件，就求背包容量
  i从1循环到256*256,用背包处理得到f数组，并记录找出值为false的下标最大元素
  在上面求出的所有数中取最小值，这就是容量
  若没有满足条件的元素，输出0，否则输出其下标

举一个例子：

不能表示成5x+3y(x,y为非负整数)的最大整数是？
答案是7 显然在1~10中，符合题意的最大数为7，对于更大的数，显然不能是3或5的倍数，而任意的数模3余1或2，余1的，可以将3×3＋1换成5×2，余2的，可以将3＋2换成5，通过这种变换可以将十以上的数都变成5x＋3y这种形式，所以满足题意的数是7

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int M=256*256;
int n,ans=0;
bool f[M+10];
int  a[20];
int main()
{
    cin>>n;
    f[0]=true; 
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=M;i++)
        for (int j=1;j<=n;j++)
        if (i>=a[j]) f[i]|=f[i-a[j]];
    for (int i=M;i>=1;i--)
        if (!f[i]) {ans=i;break;}
    if (ans>M-2*256) ans=0;
    cout<<ans<<endl;
}