uva11754 中国剩余定理+暴力搜索

是当y的组合数较小时，暴力枚举所有组合，然后用中国剩余定理求每种组合的解，对解进行排序即可

注意初始解可能是负数，所以如果凑不够S个，就对所有解加上M,2M。。。。

当y的组合数较大时，选择一个k/x最小的序列，枚举N=x*t+y，外层枚举t，内层枚举y，然后验证N是否是可行解

为什么要选k/x最小的：就是相对于x，k越小越好，使更多机会枚举t，

#include<bits/stdc++.h>
#include<vector>
#include<set>
using namespace std;
#define maxn 105
#define ll long long

int c,s,x[maxn],k[maxn],y[maxn][maxn],now;
set<int> value[maxn];
vector<ll> ans;
ll a[maxn];

//以下是枚举N的解法,找到 k/x 最小的条件，按照t=0,1,2..的顺序枚举 N = X*t+Y 
void solve_enum(){
    for(int i=0;i<c;i++){
        if(c==now)continue;
        value[i].clear();
        for(int j=0;j<k[i];j++)
            value[i].insert(y[i][j]);//放到集合里去重 
    }
    
    for(int t=0;;t++){
        for(int i=0;i<k[now];i++){
            ll n=(ll)x[now]*t+y[now][i];
            if(n==0)continue;
            
            //验证n是否是可行解 
            bool ok=1;
            for(int i=0;i<c;i++){
                if(i==now)continue;
                if(!value[i].count(n%x[i])){
                    ok=0;
                    break;
                }
            }
            
            if(ok){
                cout<<n<<endl;
                if(--s==0)return;
            }
        } 
    }
}


//以下是暴力枚举每个组合方案的解法 
long long exgcd(long long a, long long b, long long &x, long long &y) {//比较好的exgcd() 
    if (!b) {x = 1; y = 0; return a;}
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x;
     return d;
}
ll china(){//mx+ny=1
    ll M=1,ans=0;
    for(int i=0;i<c;i++)M*=x[i];
    for(int i=0;i<c;i++){
        ll w=M/x[i],xx,yy;
        exgcd(x[i],w,xx,yy);//拓展欧几里得解出 
        ans=(ans+w*yy*a[i])%M;                     
    }
    return (ans+M)%M;
}

void dfs(int d){
    if(d==c){
        ans.push_back(china());//用中国剩余定理求出当前组合的结果 
        return;
    }
    for(int i=0;i<k[d];i++){
        a[d]=y[d][i];
        dfs(d+1);
    }
}
void solve_china(){
    ans.clear();
    dfs(0);//一轮搜索出组合内的所有可行解 
    sort(ans.begin(),ans.end());//排序答案 
    ll M=1;
    for(int i=0;i<c;i++)M*=x[i];
    
    for(int i=0;;i++)
        for(int j=0;j<ans.size();j++){
            ll n=M*i+ans[j];
            if(n>0){
                cout<<n<<endl;
                if(--s==0)
                    return;
            }
        }
}

int main(){
    while(cin>>c>>s && c && s){
        now=0;
        ll sum=1;
        for(int i=0;i<c;i++){
            cin>>x[i]>>k[i];
            sum*=k[i];
            if(k[i]*x[now]<k[now]*x[i])
                now=i;//找到k/x最小的条件，按照t=0,1,2..的顺序枚举 N = X*t+Y 
            for(int j=0;j<k[i];j++)
                cin>>y[i][j];
            sort(y[i],y[i]+k[i]);//从小到大排序 
        }
        if(sum>10000)
            solve_enum();//当y组合较多时直接枚举N 
        else solve_china();//当y组合不是很多时枚举所有可能 
        puts("");
    }
}