UVa 10717 - Mint

10717.cpp

#include <bits/stdc++.h>
using namespace std;

template <class T> int size(const T &x) {return x.size();}
template <class T> T mod(T a, T b) { return (b + (a % b)) % b;}

#define F first
#define S second
#define PB push_back
#define endl '\n'
#define rep(i, a, b) for(__typeof(a) i=a; i<(b); i++)
#define iter(it, c) for(__typeof((c).begin()) it=(c).begin(); \
 it != (c).end(); it++)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;

const int INF = ~(1 << 31);
const double EPS = 1e-9;
const double PI = acos(-1);

const ll MX = 2e7 + 7;
ll LCM = INF;

void sm(vi &A, int c) {

    ll lcm;
    int a=-1, b=-1;

    for(int i=0; i<size(A); i++) {
        for(int j=i+1; j<size(A); j++) {
            for(int k=j+1; k<size(A); k++) {
                for(int l=k+1; l<size(A); l++) {

                    lcm = (ll)A[i] * (A[j] / __gcd(A[i], A[j]));
                    lcm = lcm * (A[k] / __gcd(lcm, (ll)A[k]));
                    lcm = lcm * (A[l] / __gcd(lcm, (ll)A[l]));

                    int p = c / lcm;
                    int aa = lcm*p, bb = lcm*(p+1);

                    if(a == -1 || (aa > a)) a = aa;
                    if(b == -1 || (bb < b)) b = bb;
                    if(c % lcm == a) a = b = c;

                }
            }
        }
    }

    cout << a << ' ' << b << endl;

}

int main() {

    int n, t, q;
    while(cin >> n >> t && (n + t)) {
        vi C(n);
        for(int &i : C) cin >> i;

        for(int i=0; i<t; i++) {
            cin >> q;
            sm(C, q);
        }

    }
    return 0;
}