对于一个正整数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]的形式。复杂度未知,但总方案数很大的时候可以较快得出答案。
可以用分块的思想,设定一个合适的阈值,当总方案数超过某个阈值的时候用枚举,否则就用中国剩余定理。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const ll N=9+2; 6 vector<ll> v[N],w; 7 set<ll> st[N]; 8 ll m[N],e[N],n,k,K; 9 10 void exgcd(ll a,ll b,ll& x,ll& y,ll& g) { 11 if(!b)x=1,y=0,g=a; 12 else exgcd(b,a%b,y,x,g),y-=x*(a/b); 13 } 14 15 ll inv(ll x,ll mod) { 16 ll a,b,g; 17 exgcd(x,mod,a,b,g); 18 return (a+mod)%mod; 19 } 20 21 ll check(ll x) { 22 for(ll i=0; i<n; ++i)if(!st[i].count(x%m[i]))return 0; 23 return 1; 24 } 25 26 void solve1() { 27 ll p=0; 28 for(ll i=1; i<n; ++i)if(v[i].size()*m[p]<v[p].size()*m[i])p=i; 29 for(ll t=0; w.size()<k; ++t) 30 for(ll i=0; i<v[p].size()&&w.size()<k; ++i) 31 if(t*m[p]+v[p][i]&&check(t*m[p]+v[p][i]))w.push_back(t*m[p]+v[p][i]); 32 } 33 34 void solve2() { 35 ll M=1; 36 for(ll i=0; i<n; ++i)M*=m[i]; 37 for(ll i=0; i<n; ++i)e[i]=M/m[i]*inv(M/m[i],m[i]); 38 for(ll S=0; S<K; ++S) { 39 ll S2=S,x=0; 40 for(ll i=0; i<n; ++i) { 41 ll j=S2%v[i].size(); 42 S2/=v[i].size(); 43 x=(x+e[i]*v[i][j])%M; 44 } 45 w.push_back(x?x:x+M); 46 } 47 sort(w.begin(),w.end()); 48 w.resize(unique(w.begin(),w.end())-w.begin()); 49 for(ll i=0; w.size()<k; ++i)w.push_back(w[i]+M); 50 } 51 52 int main() { 53 while(scanf("%lld%lld",&n,&k)&&n) { 54 for(ll i=0; i<N; ++i)v[i].clear(); 55 for(ll i=0; i<N; ++i)st[i].clear(); 56 K=1; 57 for(ll i=0; i<n; ++i) { 58 scanf("%lld",&m[i]); 59 ll t; 60 scanf("%lld",&t); 61 K*=t; 62 while(t--) { 63 ll x; 64 scanf("%lld",&x); 65 v[i].push_back(x); 66 st[i].insert(x); 67 } 68 sort(v[i].begin(),v[i].end()); 69 } 70 w.clear(); 71 K>10000?solve1():solve2(); 72 for(ll i=0; i<k; ++i)printf("%lld\n",w[i]); 73 printf("\n"); 74 } 75 return 0; 76 }