P - Code Feat————中国剩余定理+枚举

桃扇骨 2024-04-18 15:24 45阅读 0赞

[题解][Link 1]  
[题目链接][Link 2]

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxc = 15;
    ll c, s;// c个式子 要s个答案
    ll total, bestc;
    ll x[15], k[15], y[15][105];
    
    
    set<ll>vis[15];
    
    void init()//*
    { 
        total = 1;// total 是 x的乘积
        bestc = 0;
        for(ll i = 0; i < c; i++)
        { 
            cin>>x[i]>>k[i];
            total*=k[i];
    
            for(ll j = 0; j < k[i]; j++)
            { 
                cin>>y[i][j];
            }
    
            sort(y[i], y[i]+k[i]);// 从小到大排序
            if(k[i]*x[bestc] < k[bestc]*x[i])/***找基准 k/x 最小的为基准**/
            { 
                bestc = i;
    
            }
    
        }
    }
    
    
    void solveEnum(ll bas)//
    { 
        for(ll i = 0; i < c; i++)
        { 
            if(i == bas)continue;
    
            vis[i].clear();
            for(ll j = 0; j <k[i]; j++)
            { 
                vis[i].insert(y[i][j]);
            }
        }
        for(ll t = 0; s; t++)
        { 
            for(ll i = 0; i < k[bas]; i++)
            { 
                ll n = x[bas]*t+y[bas][i];// 找答案
    
                if(n == 0)
                { 
                    continue;
                }
    
                bool flag = true;
                for(ll z = 0; z < c; z++)
                { 
                    if(z == bas)continue;
                    if(!vis[z].count(n%x[z]))// 判断答案是否满足题目要求
                    { 
                        flag = false;
                        break;
                    }
    
                }
                if(flag)
                { 
                    cout<<n<<endl;
                    if(--s == 0)break;
                }
            }
    
        }
    
    
    }
    
    
    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);
        }
    }
    ll a[15];// a数组是选取一组 模
    ll China (ll n, ll* s, ll* m)// 中国剩余定理
    { 
        ll M = 1, d, y, x = 0;
    
        for (ll i = 0; i < n; i++)
            M *= m[i];
    
        for (ll 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;
    }
    
    
    
    vector<ll>sol;// 答案
    
    void dfs(ll dep)// dfs 组合 模 *
    { 
        if(dep == c)// 到边界时 用这组模 进行中国剩余定理
        { 
            sol.push_back(China(c, a, x));
        }
        else
        { 
            for(ll i = 0; i < k[dep]; i++)
            { 
                a[dep] = y[dep][i];
                dfs(dep+1);
            }
        }
    }
    
    
    
    void solveChina()// 利用CRT求 的过程 *
    { 
        sol.clear();
        dfs(0);
        sort(sol.begin(), sol.end());
    
        ll M = 1;
        for(ll i = 0; i < c; i++)
        { 
            M*=x[i];
        }
    
        /******求出解 存在sol 中， 可能sol 中的解不够 ， 所以再加上 i个M 得到下一组解***********/
        for(ll i = 0; s; i++)
        { 
            for(ll j = 0; j <sol.size(); j++) /**？*/
            { 
                ll n = M*i+sol[j];
                if(n > 0)// 要的是正整数答案
                { 
                    cout<<n<<endl;
                    if(-- s == 0)break;
                }
            }
        }
    
    
    }
    
    
    
    int main()
    { 
        ios_base::sync_with_stdio(false);
    
        while(cin>>c>>s&&(c||s))
        { 
            init();
    
            if(total <= 10000)solveChina();
            else solveEnum(bestc);
    
            cout<<endl;
        }
    
        return 0;
    }

[Link 1]: https://blog.csdn.net/keshuai19940722/article/details/36213067
[Link 2]: https://vjudge.net/problem/UVA-11754