记录编号	85787	评测结果	AAAAAAAAAA
题目名称	[UVa 11754] 数论难题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2014-01-12 11:39:12	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const ll SIZEC=10,LIMIT=10000;
ll X[SIZEC]={0};
multiset<ll> Y[SIZEC];//描述条件
ll C,S;//C个条件,输出前S项
void enum_solve(void){
	ll best=0,i;
	multiset<ll>::iterator key;
	for(i=1;i<C;i++) if(Y[i].size()*X[best]<Y[best].size()*X[i]) best=i;//best里是k/X最小的那个条件
	priority_queue<ll,vector<ll>,greater<ll> > tque;//尝试的队列,小根堆
	for(key=Y[best].begin();key!=Y[best].end();key++) tque.push(*key);
	ll tot=0;
	while(tot<S){
		ll temp=tque.top();tque.pop();tque.push(temp+X[best]);
		if(temp==0) goto NEXT;
		for(i=0;i<C;i++) if(Y[i].find(temp%X[i])==Y[i].end()) goto NEXT;
		tot++;
		printf("%lld\n",temp);
		NEXT:;
	}
	printf("\n");
}
multiset<ll> answer;
void extend_gcd(ll a,ll b,ll &x,ll &y,ll &d){//扩展欧几里得
	if(b==0){x=1,y=0,d=a;}
	else{extend_gcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
ll M;//在本题中,模的数之乘积是给定的,因而作为一个不会更改的变量
ll China(ll a[],ll m[],ll n){//方程的解满足条件:模m[i]的值是a[i],i从0到n
	ll ans=0,d,x,y,w;
	for(ll i=0;i<n;i++){
		w=M/m[i];
		extend_gcd(w,m[i],x,y,d);
		ans+=w*x*a[i];
		ans%=M;
	}
	return (ans+M)%M;
}
ll dtr[SIZEC]={0};//确定的余数列
void DFS(int x){//当前将确定第x个条件到底遵循哪个,下标从0开始
	if(x==C){
		ll nowans=China(dtr,X,C);
		answer.insert(nowans);
		return;
	}
	multiset<ll>::iterator key;
	for(key=Y[x].begin();key!=Y[x].end();key++){
		dtr[x]=(*key);
		DFS(x+1);
	}
}
void China_solve(void){//用中国剩余定理求解
	answer.clear();
	M=1;
	for(ll i=0;i<C;i++) M*=X[i];
	DFS(0);
	ll tot=0;
	multiset<ll>::iterator key=answer.begin();
	while(tot<S){
		if(*key){
			tot++;
			printf("%lld\n",*key);
		}
		answer.insert((*key)+M);
		key++;
	}
	printf("\n");
}
void self_adaption(void){//根据具体情况机智地选择求解方式
	ll eigen=1;
	for(ll i=0;i<C;i++) eigen*=Y[i].size();
	if(eigen<LIMIT) China_solve();
	else enum_solve();
}
bool read(void){
	scanf("%lld%lld",&C,&S);
	if(C==0&&S==0) return false;
	ll i,j,k,temp;
	for(i=0;i<C;i++){
		scanf("%lld%lld",&X[i],&k);
		Y[i].clear();
		for(j=0;j<k;j++) scanf("%lld",&temp),Y[i].insert(temp);
	}
	return true;
}
int main(){
	freopen("codefeat.in","r",stdin);
	freopen("codefeat.out","w",stdout);
	while(read()) self_adaption();
	return 0;
}