最新消息:点击查看大S的省钱秘笈

12•9大合唱 C语言版

编程相关 Slyar 45浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

学校OJ上的一道题,感觉技巧性比较强,背景就是韩信点兵,俗称中国剩余定理,帖代码出来,有同学要。

描述 Description

老师准备给大家安排一下合唱队形,可是却遇到一个问题。老师并不知道一共来了多少同学,但当他让同学们p1人一排时,多出来r1个同学;如果p2人一排,又会多出来r2个同学……就这样排了好几次都没成功。折腾了好久,老师觉得这样子太麻烦,不如再找来一些同学,让同学们站成一个方阵(行和列相等),这样就省事多了。
老师想知道最少需要再找多少同学才能使大家组成一个方阵。

输入格式 Input Format

第一行输入一个整数T,表示一共有T组测试数据。
每组测试数据第一行包含一个整数n (1<=n<=10),表示老师一共让同学们排了n次队。接下来的n行,每行输入两个整数pi ri (1<=ri<=pi<=25),表示此次排队pi个同学一排,并且多出来ri个同学。
保证输入的pi两两互质。

输出格式 Output Format

每组测试数据输出一行,输出一个整数s,表示最少需要找来s个同学就能组成方阵。
注意,同学的总人数可能有多个解,你需找出最小的一个解,并输出对应的s。

Tip:由于数据规模比较大,普通的枚举是不行的,因此需要优化。对每一组数据处理时要保证之前的数据符合题意,数学问题。最后输出的时候要注意本题存在一个人都不缺的情况。

转载请注明:Slyar Home » 12•9大合唱 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址