描述
我国古代《孙子算经》中，记有如下算题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”并给出得数：“答曰：23。”
为解决这个问题民间流传了如下歌诀：“三人同行七十稀，五树梅花廿一枝，七子团员正半月，除百零五便得知。”
把上面的问题说得明白一点就是：有一个正整数N，除以3的余数是2，除以5的余数是3，除以7的余数是2，要求这个数。
民间给出的解法是：把N除以3的余数乘以70，把N除以5的余数乘以21，把N除以7的余数乘以15，把这三个结果加起来，最后把得到的结果除以105得到的就是答案（能满足条件的最小数）。
其实在民间的解法中不除以105得到的也是一个符合题意的答案，而且民间的解法对于已知“除以3的余数，除以5的余数和除以7的余数” 的问题都能得到一个符合要求的答案。比如对于上面的问题，得到的结果是2 * 70 + 3 * 21 + 2 * 15 = 233，这个结果也能满足除以3的余数是2，除以5的余数是3，除以7的余数是2。如果已知的问题是“除以3的余数是1，除以5的余数是4，除以7的余数是4”，民间解法得到的结果1 * 70 + 4 * 21 + 4 * 15 = 214，这个结果也满足除以3的余数是1，除以5的余数是4，除以7的余数是4。
问题总结：根据3 ,5, 7求得70,21,15
把这个问题推广到更普遍的情况：
孙子问题：对于给定的正整数a1, a2, ... an，是否存在正整数b1, b2, ... bn，使得对于任意的一个正整数N，如果用N除以a1的余数是p1，用N除以a2的余数是p2……用N除以an的余数是pn，那么M = p1 * b1 + p2 * b2 + ... + pn * bn能满足M除以a1的余数也是p1，M除以a2的余数也是p2……M除以an的余数也是pn。
输入输入包括多组测试数据，每组数据包括一行。在每组数据中，首先给出ai的个数n (1 <= n <= 10)，然后给出n个不大于50的正整数a1, a2, ... an。最后一组测试数据中n = 0，表示输入的结束，这组数据不用处理。
输出
对于每一组测试数据，输出一行，如果存在正整数b1, b2, ... bn满足题意，则输出这n个正整数（数的长度不要超过50位）如果有多组答案，输出任意一组即可，相邻的正整数之间用一个空格隔开；否则，输出“NO”。
样例输入
3 3 5 7
0
样例输出
70 21 15提示
问题总结：根据a1, a2, ... an求b1, b2, ... bn的过程，与N ，M无关
求b1的过程：
求a2, ... an的最小公倍数，如果a2, ... an的最小公倍数除以a1余1，则b1等于a2, ... an的最小公倍数，否则求最小公倍数的1,2,3....ai-1倍，找到除以 a1余1的数，b1即等于该数,如果还没有找到除以 a1余1的数,就b1不存在。
问题：为什么要求a2, ... an的最小公倍数？
解决：
以3,5,7为例
假设n1%3=2 n2%5=3 n3%7=2
由于有数学定理： 如果a%b=c 那么(a+k*b)%b=c; 如果n1+n2+n3满足除以3余2，除以5余3，除以7余2，那么n1需要是5,7的倍数，同时n1除以3余2，n2是3,7的你倍数，同时除以5余3，n3是3,5 的倍数同时除以7余2
问题：求过5,7最小公倍数，为什么要找最小公倍数的倍数除以3余1的数
解决：
因为上面条件说了n1需要是5,7的倍数，同时n1除以3余2
数学定理：如果a%b=1, 也就是说（k*b+1）%b=1 那么n*（k*b+1）%b=1*n;(n<b)
推广求bi的过程：
求除ai外的n-1个元素的最小公倍数，如果最小公倍数除以ai余1，则bi等于最小公倍数，否则求最小公倍数的1,2,3....倍，找到除以 ai余1的数，bi即等于该数，如果还没有找到除以 ai余1的数,就bi不存在。
求b1过程解析：
以3,5,7求70,21,15的过程为例
1. 5,7的最小公倍数(35)+3,7的最小公倍数(21)+3,5的最小公倍数(15)的值是3,5,7的公倍数
2. 5,7的最小公倍数（35）除以3余2，35*2=70除以3余1，也就是说3*n+1=70 所以（3*n+1）*2%3==2 即（3*n+1）*余数%3==余数
3. 此时b1的值就是70=5*7*2；除以5,7能除尽，同时除以3余1.
以上求得bi的值一定满足p1 * b1 + p2 * b2 + ... + pn * bn的结果M除以a1的余数为p1，除以a2的余数为p2……除以an的余数为pn。但是不是最小值，例如5*7+3*7*3+3*5*2=128也满足除以3余2，除以5余3.，除以7余2，因为5,7的最小公倍数除以3正好余2，所以不用乘以2，但是上面的求bi的方法是统一的方法。
孙子问题源程序：
import .*;
public class LX3 {
private static int n;//整数的个数
private static int[] a;//保存n个整数a1,a2.....an
private static int[] b;//保存n个整数b1,b2.....bn
private static int[] b1;//保存n个整数，每个整数分别代表除ai值外的数的最小公倍数
private static int[] tp;//在求bi的时候的辅助数组
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner();
n=();
a=new int[n];
b=new int[n];
b1=new int[n];
tp=new int[n];
for(int i=0;i<n;i++)
{
a[i]=();
}
for(int i=0;i<n;i++)
{
for(int p=0;p<n;p++)//数组a中的元素不能改变，但是在求最小公倍数的时候需要改变元素的值所以
//没求一次最小公倍数需要给临时数组tp重新赋予a数组的值
{
tp[p]=a[p];
}
MinCommonMutiply(i);
//(b1[i]);
}
for(int i=0;i<n;i++)
{
if(b1[i]%a[i]==1)
{
b[i]=b1[i];
(b[i]+" ");
}
else
{
int m=0;
for( m=2;m<a[i];m++)
{
if(b1[i]*m%a[i]==1)
{
b[i]=b1[i]*m;
(b[i]+" ");
break;
}
}
if(m==a[i])//没有的到除以a[i]余1的数
{
("NO"+" ");
}
}
}
}
public static void MinCommonMutiply(int i)//除了a[i]之外的数的最小公倍数
{
int temp1=tp[i];
tp[i]=1;
int yinzi=1;
for(int j=0;j<n-1;j++)
{
for(int k=j+1;k<n;k++)
{
int num1,num2;
if(tp[j]<tp[k])//两数最大数保存在 num1中
{
num1=tp[k];
num2=tp[j];
}
else
{
num1=tp[j];
num2=tp[k];
}
while(num2!=0)
{
int temp=num1%num2;
num1=num2;
num2=temp;
}
tp[j]/=num1;
tp[k]/=num1;
yinzi*=num1;
//(j+" "+k+" "+a[j]+" "+a[k]+" "+yinzi);
}
}
//(yinzi);
for(int j=0;j<n;j++)
{
yinzi*=tp[j];
}
b1[i]=yinzi;
}
}