UVA 11754 Code Feat中国の残りの定理+普通の列挙
2656 ワード
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define LL long long
#define limit 10000
LL n,m,x[11],y[11][111],a[11],M,c;
vector<LL>e;
set<LL>f[11];
void gcd(LL a,LL b,LL &d,LL &xx,LL &yy)// , ax+by=gcd(a,b)
{
if(!b){d=a;xx=1;yy=0;}
else{gcd(b,a%b,d,yy,xx);yy-=xx*(a/b);}
}
LL china(LL a[])// , M%A=a,M%B=b,... M, A,B,C...
{
LL i,j,k,d,ans=0,xx,yy;
for(i=0;i<n;i++)
{
k=M/x[i];
gcd(x[i],k,d,xx,yy);
ans=(ans+yy*k*a[i])%M;
}
return (ans+M)%M;
}
void dfs(LL t)
{
LL i,j,k;
if(t==n)
e.push_back(china(a));
for(i=1;i<=y[t][0];i++)
{
a[t]=y[t][i];
dfs(t+1);
}
}
void slove()
{
LL i,j,k=0;
e.clear();
dfs(0);
sort(e.begin(),e.end());
for(i=0;;i++)
{
for(j=0;j<e.size();j++)
{
LL ss=M*i+e[j];
if(ss>0)
{
//cout<<M*i+e[j]<<endl;
printf("%lld
",ss);
k++;
}
if(k==m)
return;
}
}
//cout<<endl;
}
void slove2()
{
LL i,j,k,p,q=0;
for(i=0;i<n;i++)
{
if(i!=c)
{
f[i].clear();
for(j=1;j<=y[i][0];j++)
f[i].insert(y[i][j]);
}
}
for(i=0;;i++)
{
for(j=1;j<=y[c][0];j++)
{
p=x[c]*i+y[c][j];
if(p==0)continue;
for(k=0;k<n;k++)
if(c!=k&&!f[k].count(p%x[k]))break;
if(k>=n)
{
printf("%lld
",p);
q++;
if(q==m)
return;
}
}
}
}
int main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)
{
LL i,j,k,t=1;
if(n==0&&m==0)
break;
M=1;
c=0;
for(i=0;i<n;i++)
{
scanf("%lld%lld",&x[i],&y[i][0]);
M=M*x[i];
t=t*y[i][0];
for(j=1;j<=y[i][0];j++)
scanf("%lld",&y[i][j]);
sort(y[i]+1,y[i]+y[i][0]+1);// ,
if(y[i][0]*x[c]>y[c][0]*x[i])c=i;//ki/xi>kc/xc
}
if(t>limit)slove2();// ,k/x , t*x+yi ,
else slove();// , dfs 10000 ,
printf("
");
}
return 0;
}