文章作者：姜南(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:由于数据规模比较大，普通的枚举是不行的，因此需要优化。对每一组数据处理时要保证之前的数据符合题意，数学问题。最后输出的时候要注意本题存在一个人都不缺的情况。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <stdio.h> #include <math.h> int main(){ int i,j,k,t,n,p,r,sum; scanf("%d",&t); while(t--){ sum=0; j=1; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d",&p,&r); while(sum%p!=r) sum+=j; j*=p; //保证sum对前面的p求余结果仍然为r } k=sqrt(sum); if(k!=sqrt(sum)) k+=1; //有一个人都不缺的情况 printf("%d\n",k*k-sum); } return 0; } |
转载请注明：Slyar Home » 12•9大合唱 C语言版