对于一个正整数 N, 给出 C 组限制条件, 每组限制条件为 N%X[i]∈{Y1,Y2,Y3,...,Yk[i]}, 求满足条件的前 S 小的 N.
这道题很容易想到用中国剩余定理, 然后用求第 k 小集合的方法输出答案. 但是一取模, 孰大孰小就不好控制了, 所以行不通. 直接枚举所有情况的话, 总方案数 (所有 k 的乘积) 高达 C*k, 显然也是不行的.
还有一种方法是枚举所有可能的 N, 然后检验是否满足条件. 对于每个满足条件的 N, 任取某个限制条件 i, 对于其中某个余数 j, 都可以写成 X[i]*t+Y[i][j]的形式. 复杂度未知, 但总方案数很大的时候可以较快得出答案.
可以用分块的思想, 设定一个合适的阈值, 当总方案数超过某个阈值的时候用枚举, 否则就用中国剩余定理.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll N=9+2;
- vector<ll> v[N],w;
- set<ll> st[N];
- ll m[N],e[N],n,k,K;
- void exgcd(ll a,ll b,ll& x,ll& y,ll& g) {
- if(!b)x=1,y=0,g=a;
- else exgcd(b,a%b,y,x,g),y-=x*(a/b);
- }
- ll inv(ll x,ll mod) {
- ll a,b,g;
- exgcd(x,mod,a,b,g);
- return (a+mod)%mod;
- }
- ll check(ll x) {
- for(ll i=0; i<n; ++i)if(!st[i].count(x%m[i]))return 0;
- return 1;
- }
- void solve1() {
- ll p=0;
- for(ll i=1; i<n; ++i)if(v[i].size()*m[p]<v[p].size()*m[i])p=i;
- for(ll t=0; w.size()<k; ++t)
- for(ll i=0; i<v[p].size()&&w.size()<k; ++i)
- if(t*m[p]+v[p][i]&&check(t*m[p]+v[p][i]))w.push_back(t*m[p]+v[p][i]);
- }
- void solve2() {
- ll M=1;
- for(ll i=0; i<n; ++i)M*=m[i];
- for(ll i=0; i<n; ++i)e[i]=M/m[i]*inv(M/m[i],m[i]);
- for(ll S=0; S<K; ++S) {
- ll S2=S,x=0;
- for(ll i=0; i<n; ++i) {
- ll j=S2%v[i].size();
- S2/=v[i].size();
- x=(x+e[i]*v[i][j])%M;
- }
- w.push_back(x?x:x+M);
- }
- sort(w.begin(),w.end());
- w.resize(unique(w.begin(),w.end())-w.begin());
- for(ll i=0; w.size()<k; ++i)w.push_back(w[i]+M);
- }
- int main() {
- while(scanf("%lld%lld",&n,&k)&&n) {
- for(ll i=0; i<N; ++i)v[i].clear();
- for(ll i=0; i<N; ++i)st[i].clear();
- K=1;
- for(ll i=0; i<n; ++i) {
- scanf("%lld",&m[i]);
- ll t;
- scanf("%lld",&t);
- K*=t;
- while(t--) {
- ll x;
- scanf("%lld",&x);
- v[i].push_back(x);
- st[i].insert(x);
- }
- sort(v[i].begin(),v[i].end());
- }
- w.clear();
- K>10000?solve1():solve2();
- for(ll i=0; i<k; ++i)printf("%lld\n",w[i]);
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945874.html