uva 11754 - Code Feat(中國剩余定理+暴力)

題目鏈接：uva 11754 - Code Feat

題目大意：求一個數N，給出C和S，表示有C個條件，每個條件有X 和 k，然後是該個條件的k個yi，即NmodX=yj,輸出滿足的最小的S個N，要求正整數。

解題思路：total為所有的k的乘積，也就是可以作為一組完整限定條件的可能數，當個確定條件可以用中國剩余定理處理。但是如果total太大的話，處理的情況比較多。不過total數大的時候，可以通過枚舉N來判斷，找到一組k/x最小的最為枚舉基准，然後判斷即可。

#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int maxc = 15;
const int maxk = 105;
const int limit = 10000;

ll total;
int C, S, X[maxc], k[maxc];
int bestc, Y[maxc][maxk];
set vis[maxc];

void init () {
    total = 1;
    bestc = 0;
    for (int i = 0; i < C; i++) {
        scanf("%d%d", &X[i], &k[i]);
        total *= k[i];

        for (int j = 0; j < k[i]; j++)
            scanf("%d", &Y[i][j]);
        sort(Y[i], Y[i] + k[i]);

        if (k[i] * X[bestc] < k[bestc] * X[i])
            bestc = i;
    }
}

void solveEnum (int s) {

    for (int i = 0; i < C; i++) {
        if (i == s)
            continue;

        vis[i].clear();
        for (int j = 0; j < k[i]; j++)
            vis[i].insert(Y[i][j]);
    }

    for (int t = 0; S; t++) {

        for (int i = 0; i < k[s]; i++) {
            ll n = (ll)X[s] * t + Y[s][i];

            if (n == 0)
                continue;

            bool flag = true;
            for (int c = 0; c < C; c++) {
                if (c == s)
                    continue;

                if (!vis[c].count(n%X[c])) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                printf("%lld\n", n);
                if (--S == 0)
                    break;
            }
        }
    }
}

int a[maxc];
vector sol;

void gcd(ll a, ll b, ll& d, ll& x,ll& y) {
    if (!b) {
        d = a;
        x = 1;
        y = 0;
    } else {
        gcd(b, a%b, d, y, x);
        y -= x*(a/b);
    }
}

int china (int n, int* s, int* m) {
    ll M = 1, d, y, x = 0;

    for (int i = 0; i < n; i++)
        M *= m[i];

    for (int i = 0; i < n; i++) {
        ll w = M / m[i];
        gcd(m[i], w, d, d, y);
        x = (x + y * w * a[i]) % M;
    }
    return (x+M)%M;
}

void dfs (int dep) { 
    if (dep == C)
        sol.push_back(china(C, a, X));
    else {
        for (int i = 0; i < k[dep]; i++) {
            a[dep] = Y[dep][i];
            dfs(dep+1);
        }
    }
}

void solveChina () {
    sol.clear();
    dfs(0);
    sort(sol.begin(), sol.end());

    ll M = 1;
    for (int i = 0; i < C; i++)
        M *= X[i];

    for (int i = 0; S; i++) {
        for (int j = 0; j < sol.size(); j++) {
            ll n = M * i + sol[j];
            if (n > 0){
                printf("%lld\n", n);
                if (--S == 0)
                    break;
            }
        }
    }
}

int main () {
    while (scanf("%d%d", &C, &S) == 2 && C + S) {
        init();

        if (total > limit)
            solveEnum(bestc);
        else
            solveChina();
        printf("\n");
    }
    return 0;
}