FJUT第四次周赛E题题解

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<stdio.h>
  2 #include<vector>
  3 #include<set>
  4 #include<algorithm>
  5 #include<stdlib.h>
  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<int >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<C;c++) if(c!=bc){
 20         values[c].clear();
 21         for(int i=0;i<k[c];i++) values[c].insert(Y[c][i]);
 22         }
 23 
 24     for(int t=0;S!=0;t++){
 25         for(int i=0;i<k[bc];i++){
 26             LL n=(LL)X[bc]*t+Y[bc][i];
 27             if(n==0) continue;
 28             bool ok=true;
 29             for(int c=0;c<C;c++) if(c!=bc)
 30             if(!values[c].count(n%X[c])) {ok=false;break;}
 31             if(ok) {printf("%lld
",n);if(--S == 0) break;}
 32         }
 33     }
 34 }
 35 
 36 int a[maxc];
 37 vector<LL>sol;
 38 
 39 ///n个方程 x=a[i](mod m[i]) (0<=i<n)
 40 
 41 void gcd(LL a ,LL b,LL &d,LL &x,LL &y ){
 42     if(!b)  {d=a;x=1;y=0;}
 43     else { gcd(b,a%b,d,y,x);y-=x*(a/b); }
 44 }
 45 
 46 LL china(int n,int *a,int *m)
 47 {
 48     LL M=1,d,y,x=0;
 49     for(int i=0;i<n;i++) M*=m[i];
 50 
 51     for(int i=0;i<n;i++){
 52         LL w=M/m[i];
 53         gcd(m[i],w,d,d,y);
 54         x=(x+y*w*a[i])%M;
 55     }
 56     return (x+M)%M;
 57 }
 58 void dfs(int dep){
 59     if(dep==C)
 60         sol.push_back(china(C,a,X));
 61     else for(int i=0;i<k[dep];i++){
 62         a[dep]=Y[dep][i];
 63         dfs(dep+1);
 64     }
 65 }
 66 
 67 void solve_china(int S){
 68     sol.clear();
 69     dfs(0);
 70     sort(sol.begin(),sol.end());
 71 
 72     LL M=1;
 73     for(int i=0;i<C;i++)M*=X[i];
 74 
 75     vector<LL> ans;
 76 
 77     for(int i=0;S!=0;i++){
 78         for(int j=0;j<sol.size();j++){
 79             LL n=M*i+sol[j];
 80             if(n>0){printf("%lld
",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<C;c++){
 97             scanf("%d %d",&X[c],&k[c]);
 98             tot*=k[c];
 99             for(int i=0;i<k[c];i++) scanf("%d",&Y[c][i]);
100 
101             sort(Y[c],Y[c]+k[c]);
102 
103             if(k[c]*X[bestc]<k[bestc]*X[c]) bestc=c;
104         }
105 
106         if(tot>LIMIT) solve_enum(S,bestc);
107         else solve_china(S);
108 
109     }
110     return 0;
111 }
112 /*
113 3 2
114 2 1 1
115 5 2 0 3
116 3 2 1 2
117 */

标程