买不到的数目（经典奥数题）

题目描述：

思路：

求n和m最大不能买到的糖数 指的是n和m组合之后最大的不能组合出的数字

• 引理：给定a,b,若d = gcd(a,b) > 1,一定不能凑出最大数 本题保证一定有解，所以不用考虑

代码部分：

• 方法一：数组暴力遍历（数据范围比较小可以AC)

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int a[MAXN];
int main ()
{
	int m,n;
	cin>>n>>m;
	a[0]=1;
	for(int i=0;i<MAXN;i++)
	{
		if(a[i-n]&&i>=n||a[i-m]&&i>=m) a[i]=1;
	}
	for(int i=MAXN-1;i>0;i--)
	{
		if(!a[i])
		{
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

• 方法二：打表（DFS)

#include <bits/stdc++.h>
using namespace std;
bool dfs(int i,int n,int m)
{
	if(i==0) return true;// 递归出口
	
	if(i>=n&&dfs(i-n,n,m)) return true;
	if(i>=m&&dfs(i-m,n,m)) return true;
	
	return false; 
}
int main ()
{
	int n,m;cin>>n>>m;
	int res=0;
	for(int i=1;i<=1000;i++)
	{
		if(!dfs(i,n,m)) res=i; 
	}
	cout<<res<<endl;
	return 0;
} 

• 方法三：数学分析

// if(gcd(p,q)>1) 一定不能凑出最大数 
// 找规律法
/*
p q m 
3 2 1   4 3 5
3 4 5   4 5 11
3 5 7   4 7 17
3 7 11  4 9 23

在p=3时，q每增加1,m将增加2,所以m=2q+x,得x=-3;m=2q-3;
       m=(p-1)q-p=pq-q-p; 
*/
#include <bits/stdc++.h>
using namespace std;
int main ()
{
	int p,q;cin>>p>>q;
	int m=p*q-p-q;
	cout<<m<<endl;
	return 0;
}

• 本体结论：两个正整数n,m，最大不能买到的数为：MAX=(p-1)*(q-1)-1;