1315: 孙子算经

Time Limit: 1 SecMemory Limit: 128 MB

---

Submit: 164Solved: 130

[Submit][Status][Web Board]

Description

      《孙子算经》中的题目：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？

《孙子算经》中的解法：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。

         解法中的三个关键数70，21，15，有何妙用，有何性质呢?首先70是3除余1而5与7都除得尽的数，所以70a是3除余a，而5与7都除得尽的数，21是5除余1，而3与7都除得尽的数，所以21b是5除余b，而3与7除得尽的数。同理，15c是7除余c，3与5除得尽的数，总加起来 70a+21b+15c 是3除余a，5除余b ，7除余c的数，也就是可能答案之一，但可能不是最小的，这数加减105（105=3×5×7）仍有这样性质，可以多次减去105而得到最小的正数解。

    现在给定4个互不相等的被除数数A,B,C,D(0<A,B,C,D<50)和4个余数a,b,c,d(0<a<A,0<b<B,0<c<C,0<d<D)，求最小的正除数，题目保证有正解。

Input

有多组数据，每组数据有4个被除数A,B,C,D和4个余数a,b,c,d。

Output

输出相应的答案，占一行。

Sample Input

2 3 5 7 1 2 3 4

29 31 37 43 13 14 15 16

Sample Output

53

600081

---

ZCMU1315: 孙子算经 - zjykshen的博客 - CSDN博客

#include<stdio.h>

#include<iostream>

#include<math.h>

int main(){

int i,a,b,c,d,A,B,C,D;

long long prom;

while(~scanf("%d%d%d%d%d%d%d%d",&A,&B,&C,&D,&a,&b,&c,&d)){

for(i=1;;i++){

prom=i;

if(prom%A==a&&prom%B==b&&prom%C==c&&prom%D==d)

break;

}

printf("%lld\n",prom);

}

return 0;

}