HDU 1788 Chinese remainder theorem again

Description

我知道部分同學最近在看中國剩餘定理，就這個定理本身，還是比較簡單的： 

假設m1,m2,…,mk兩兩互素，則下面同餘方程組： 

x≡a1(mod m1) 

x≡a2(mod m2) 

… 

x≡ak(mod mk) 

在0<=<m1m2…mk内有唯一解。 

記Mi=M/mi(1<=i<=k),因為（Mi,mi）=1,故有二個整數pi,qi滿足Mipi+miqi=1,如果記ei=Mi/pi,那麼會有： 

ei≡0(mod mj),j!=i 

ei≡1(mod mj),j=i 

很顯然，e1a1+e2a2+…+ekak就是方程組的一個解，這個解加減M的整數倍後就可以得到最小非負整數解。 

這就是中國剩餘定理及其求解過程。 

現在有一個問題是這樣的： 

一個正整數N除以M1餘(M1 - a)，除以M2餘(M2-a), 除以M3餘(M3-a),總之， 除以MI餘(MI-a),其中（a<Mi<100 i=1,2,…I）,求滿足條件的最小的數。 

Input

輸入資料包含多組測試執行個體，每個執行個體的第一行是兩個整數I(1<I<10)和a,其中，I表示M的個數，a的含義如上所述，緊接着的一行是I個整數M1,M1...MI，I=0 并且a=0結束輸入，不處理。 

Output

對于每個測試執行個體，請在一行内輸出滿足條件的最小的數。每個執行個體的輸出占一行。 

Sample Input

2 1
2 3
0 0      

Sample Output

5

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 9973;
const int N = 3e5 + 10;
int n, a;
LL ans, x;

LL gcd(LL x, LL y)
{
  return x%y ? gcd(y, x%y) : y;
}

int main()
{
  while (scanf("%d%d", &n, &a), n + a)
  {
    ans = 1;
    while (n--)
    {
      scanf("%lld", &x);
      ans = ans / gcd(x, ans) * x;
    }
    printf("%lld\n", ans - a);
  }
  return 0;
}