http://acm.hdu.edu.cn/showproblem.php?pid=2566
假设一堆由1分、2分、5分组成的n个硬币总面值为m分，求一共有多少种可能的组合方式（某种面值的硬币可以数量可以为0）。
输入数据第一行有一个正整数T，表示有T组测试数据；
接下来的T行，每行有两个数n,m，n和m的含义同上。
接下来的T行，每行有两个数n,m，n和m的含义同上。
对于每组测试数据，请输出可能的组合方式数；
每组输出占一行。
每组输出占一行。
Sample Input
2
3 5
4 8
Sample Output
1
2
【题解】： 这里没有给出n，m的范围，建议使用第三种【code3】方式解
【code1】：暴力O(N*N)
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i,n,m,j;
scanf("%d%d",&n,&m);
int cnt=;
for(i=;i<=m/;i++)
{
for(j=;j<=m/;j++)
{
if(n-i-j+j*+i*==m&&n-i-j>=)
{
cnt++;
}
}
}
printf("%d\n",cnt);
}
return ;
}
【code2】：暴力 O（N）
似乎只要1、2、5，硬币的个数中的一个固定了，另外两个也就一定
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i,n,m;
scanf("%d%d",&n,&m);
int cnt=;
for(i=;i<=m/;i++)
{
int ln = n-i;
int lm = m-i*;
if(lm>=ln&&lm<=*ln)
{
cnt++;
}
}
printf("%d\n",cnt);
}
return ;
}
【code3】：优化（推荐）
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,mins,maks;
scanf("%d%d",&n,&m);
if(m>=n) maks=(m-n)/;
else
{
puts("");
continue;
}
if(m-*n>=)
{
if((m-*n)% == )
mins=(m-*n)/;
else
mins=(m-*n)/ + ;
}
else mins=;
printf("%d\n",maks-mins+);
}
return ;
}