Problem Description

Morning_X今天又在摸鱼了，因为Home_W忙着给新生上课，于是他就在偷偷的摸鱼

 

但是常在河边走哪能不湿鞋，他一不小心就被Home_W抓到了，因为Home_W上次给LIWEI出题目被解出来以后

Home_W一直在准备新的题目，用来难住这群16级的摸鱼怪，于是Home_W立刻就说出了题目：

 

Home_W要求Morning_X在1秒内立刻说出一个数字，这个数字必须满足C个条件，每个条件都形如“他除以X的余数都在集合{Y1，Y2……，Yk}中”，

Home_W说Morning_X的智商太低了，于是他降低了条件所有条件中的X两两互素，现在Morning_X把任务交给了你，因为他要继续去摸鱼了

 

你的任务就是找的最小的S个解

Input

输入包含若干组数据

 

每组数据的第一行为两个整数C和S（1<=C<=9，1<=S<=10）

以下C行，每行描述一个条件，首先是整数X和k（X>=2,1<=K<=100）,然后是（Y1,Y2……Yk）（0<=Y1,Y2……Yk<X）

所有的X的乘积保证在32位带符号整数的范围内。输入标志结束位C=S=0

Output

对于每一组数据都输出S个最小正整数解，并按照从小到大排序

 

题解：这道题目比较难处理的地方在于“除以X的余数必须在集合内”，但是题目已经告诉了我们这个集合内的元素，就比较好处理多了

比较暴力的做法就是枚举每个集合中的元素，这样子我们就可以处理样例。

1 x mod 2=1,x mod 5=0,x mod 3=1 ----->x mod 30=25;2 3 x mod 2=1,x mod 5=0,x mod 3=2 ----->x mod 30=5;4 5 x mod 2=1,x mod 5=3,x mod 3=1 ----->x mod 30 =13;6 7 x mod 2=1,x mod 5=3,x mod 3=2 ----->x mod 30=23;

`

当所有的k的乘积很大时，这种方法就很慢了，此时我们就有另外一组方法了，直接枚举x。找一个k/X的最小条件（比如样例中的k=2,X=5）

看是否满足条件，按照t=0,1,2……的顺序枚举所有的tX=Yi(相同的t按照从小到大的顺序枚举Yi)，看是否满足条件。

因为所有的k的乘积很大，这个方法很快就能找到解

 

有两个需要解决的地方。

1：如果用中国剩余定理求解，若得到的解不超过S个，需要把这些解加上M,2M,3M,……，直到解够多（M为所有解的乘积）。

2：根据题意，0不能算作解，因为它不是正整数。但不要因此把,M,2M,3M……这些解也忽略了

1 #include
         
            2 #include
          
             3 #include
           
              4 #include
            
               5 #include
             
                6 using namespace std;  7   8 typedef long long LL;  9 const int maxc=9; 10 const int maxk=100; 11 const int LIMIT=10000; 12  13 set
              
               values[maxc]; 14 int C,X[maxc],k[maxc]; 15 int Y[maxc][maxk]; 16 17 void solve_enum(int S,int bc) 18 { 19 for(int c=0;c
               
                sol; 38 39 ///n个方程 x=a[i](mod m[i]) (0<=i
                
                  ans; 76 77 for(int i=0;S!=0;i++){ 78 for(int j=0;j
                 
                  0){printf("%lld\n",n);if(--S==0)break;} 81 } 82 } 83 84 } 85 86 int main() 87 { 88 int S; 89 // freopen("C:\\Documents and Settings\\Administrator\\桌面\\E\\moyu6.in","r",stdin); 90 // freopen("C:\\Documents and Settings\\Administrator\\桌面\\E\\moyu6.out","w",stdout); 91 while(scanf("%d %d",&C,&S)!=EOF){ 92 if(C==0&&S==0) 93 break; 94 LL tot=1; 95 int bestc=0; 96 for(int c=0;c
                  
                   LIMIT) solve_enum(S,bestc);107 else solve_china(S);108 109 }110 return 0;111 }112 /*113 3 2114 2 1 1115 5 2 0 3116 3 2 1 2117 */