Skip to content

11345: 【原1345】coin

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1345 

题目描述

死神有好多硬币!一分钱的,两分钱的,三分钱的,甚至是五千分钱的。死神有每种分值的硬币若干。死神要拿出一些硬币,使得和为S分。由于死神这一天特别开心,他还希望所选取的每种分值的硬币数量相等。因为死神打前一题数据的时候花费了太多的体力,现在意识模糊的他只能够算清楚一百以内的算术。

请告诉他,一共有多少种这样的可能方案。两种方案被认为是相同的,当且仅当每种分值面额硬币的选取数目相等。

输入说明

第一行唯一的整数test,表示数据组数;

接下来test块,每块第一行两个整数S,n,意指硬币面额和与不同面额硬币的数量;

紧接着n行,每行两个整数a,b,表示每种硬币的面额与数目;

输出格式

输出test块,具体形式详见样例;

Sample input

2
10 2
2 2
6 1
10 4
1 10
2 10
3 10
4 10

Sampleoutput

Case1:0
Case2:5

数据范围

对于30%的数据,n<=2;

对于100%的数据,test<=100,S<=5000,n<=50,a,b<=5000;

a互不相同,且保证使用long long答案大概也许应该与std无异。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!