UVA 11754 code feat (中国剩余定理+暴力枚举）

题意：

给出 C , S C,S C,S， C C C代表着条件个个数， S S S代表你要输出答案的个数(因为肯定有多个答案)；

然后下面有 C C C行，每行有先是 X , k X,k X,k；然后后面紧跟着 k k k个数字。满足这个条件的情况就 是 N % X = k 1 ， k 2 . . . k i ; 是N\%X=k_{1}，k_{2}...k_{i}; 是N%X=k1​，k2​...ki​;

要你求出最小的 N N N满足这 C C C个条件；

大眼一看这个题像模线性方程组，实际上如果我们枚举模 x i x_{i} xi​的结果 y i j y_{ij} yij​，就是解模线性方程组，并且是模数互质版

这个算法在 k k k的乘积很小的时候奏效， k k k的乘积很大时枚举太慢

发现 c c c很少，实际上可以暴力枚举满足一个条件的解，再去验证是否满足其他的条件

找 k / x k/x k/x最小的那个条件，为什么？因为 k / x k/x k/x小说明模x的剩余系大，而满足的解少，这样直接枚举这少部分解就很快了。

AC代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <queue>
using namespace std;
#define sd(n) scanf("%d", &n)
#define sdd(n, m) scanf("%d%d", &n, &m)
#define sddd(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n, m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n, m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld", &n)
#define sldd(n, m) scanf("%lld%lld", &n, &m)
#define slddd(n, m, k) scanf("%lld%lld%lld", &n, &m, &k)
#define sf(n) scanf("%lf", &n)
#define sc(n) scanf("%c", &n)
#define sff(n, m) scanf("%lf%lf", &n, &m)
#define sfff(n, m, k) scanf("%lf%lf%lf", &n, &m, &k)
#define ss(str) scanf("%s", str)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define mem(a, n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mod(x) ((x) % MOD)
#define gcd(a, b) __gcd(a, b)
#define lowbit(x) (x & -x)
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
inline int read()
{
    int ret = 0, sgn = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            sgn = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    return ret * sgn;
}
inline void Out(int a) //Êä³öÍâ¹Ò
{
    if (a > 9)
        Out(a / 10);
    putchar(a % 10 + '0');
}

ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
///快速幂m^k%mod
ll qpow(ll a, ll b, ll mod)
{
    if (a >= mod)
        a = a % mod + mod;
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * a;
            if (ans >= mod)
                ans = ans % mod + mod;
        }
        a *= a;
        if (a >= mod)
            a = a % mod + mod;
        b >>= 1;
    }
    return ans;
}

// 快速幂求逆元
int Fermat(int a, int p) //费马求a关于b的逆元
{
    return qpow(a, p - 2, p);
}
void exgcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if (!b)
        d = a, x = 1, y = 0;
    else
    {
        exgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
ll china(int n, int a[], int m[])
{
    ll M = 1;
    for (int i = 1; i <= n; ++i)
        M *= m[i];
    ll ret = 0, x, y, Mi, d;
    for (int i = 1; i <= n; ++i)
    {
        Mi = M / m[i];
        exgcd(Mi, m[i], d, x, y);
        ret = (ret + a[i] * Mi * x) % M;
    }
    return (ret + M) % M;
}
const int maxc = 15;
const int maxk = 105;
int x[maxc], y[maxc][maxk], k[maxc], c, s;
vector<int> ans;
int a[maxc];
void dfs(int dep)
{
    if (dep == c + 1)
        ans.push_back(china(c, a, x));
    else
    {
        for (int i = 1; i <= k[dep]; ++i)
        {
            a[dep] = y[dep][i];
            dfs(dep + 1);
        }
    }
}

set<int> val[maxc];
int main()
{
    while (~sdd(c, s))
    {
        ll cnt = 1;
        int best = 1;
        rep(i, 1, c)
        {
            sdd(x[i], k[i]);
            cnt *= k[i];
            rep(j, 1, k[i])
                sd(y[i][j]);
            sort(y[i] + 1, y[i] + 1 + k[i]);
            if (k[i] * x[best] < k[best] * x[i])
                best = i;
        }
        if (cnt > 1e4)
        {
            rep(i, 1, c)
            {
                if (i != best)
                {
                    val[i].clear();
                    rep(j, 1, k[i])
                        val[i]
                            .insert(y[i][j]);
                }
            }
            for (int i = 0; s; ++i)
            {
                rep(j, 1, k[best])
                {
                    ll n = (ll)x[best] * i + y[best][j];
                    if (n == 0)
                        continue;
                    bool ok = 1;
                    rep(l, 1, c)
                    {
                        if (l != best && !val[l].count(n % x[l]))
                        {
                            ok = 0;
                            break;
                        }
                    }
                    if (ok)
                    {
                        pld(n);
                        if (--s == 0)
                            break;
                    }
                }
            }
        }
        else
        {
            ans.clear();
            dfs(1);
            sort(ans.begin(), ans.end());
            ll M = 1;
            rep(i,1,c)
                M *= x[i];
            for (int i = 0; s; ++i)
            {
                for (int j = 0, lim = ans.size(); j < lim; ++j)
                {
                    ll n = M * i + ans[j];
                    if (n > 0)
                    {
                        pld(n);
                        if (--s == 0)
                            break;
                    }
                }
            }
        }
        printf("\n");
    }
    return 0;
}