UVA 11754 Code Feat 中国剩余定理+枚举

Code FeatUVA - 11754

题意：给出c个彼此互质的x_i，对于每个x_i，给出ki个y_j，问前s个ans满足ans%x_i的结果在y_j中有出现过。

一看便是个中国剩余定理，但是同余方程组就有k_i的乘积种组合，而k_i的乘积最大是1e18，直接中国剩余定理肯定不是的，只能对k_i的乘积稍微小的时候才能使用。

而当k_i的乘积很大时，便说明对于每个x_i它的y_j都很多，那么我们挑选其中一组x_i，设ans=temp*x_i+y_j，temp不需要枚举到很大便能满足其他的%x_i=y_j,

至于那组x_i的选择，因为我们是要枚举得更快，所有便是y_j尽可能的多，x_i尽可能的大，也就是k_i/x_i最小。

最后注意输出格式上，空行的输出。

 #include<cstdio>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int N=;

 int n,m;

 ll bb[N],cc[N],cp;

 set<ll> ss[N];

 ll exgcd(ll a,ll b, ll &x,ll &y){

     if(!b){

         x=;

         y=;

         return a;

     }

     ll g=exgcd(b,a%b,y,x);

     y-=a/b*x;

     return g;

 }

 ll inv(ll a,ll c){

     ll g,x,y;

     g=exgcd(a,c,x,y);

     return g== ? (x%c+c)%c : -;

 }

 ll crt(){

     ll ans=,temp;

     for(int i=;i<n;i++){

         temp=cp/cc[i];

         ans+=bb[i]*temp*inv(temp,cc[i]);

         if(ans>=cp) ans%=cp;

     }

     ans=(ans+cp)%cp;

     if(!ans) ans+=cp;

     return ans;

 }

 void dfs(int x){

     if(x==n){

         ss[n].insert(crt());

         return ;

     }

     for(set<ll>::iterator it=ss[x].begin();it!=ss[x].end();it++){

         bb[x]=*it;

         dfs(x+);

     }

 }

 void solve1(){

     cp=;

     for(int i=;i<n;i++) cp*=cc[i];

     ss[n].clear();

     dfs();

     ll temp=,ans;

     while(m){

         for(set<ll>::iterator it=ss[n].begin();it!=ss[n].end();it++){

             ans=(*it)+temp*cp;

             printf("%lld\n",ans);

             m--;

             if(!m) break;

         }

         temp++;

     }

 }

 void solve2(int p){

     ll temp=,ans;

     while(m){

         for(set<ll>::iterator it=ss[p].begin();it!=ss[p].end();it++){

             ans=temp*cc[p]+(*it);

             if(!ans) continue;

             bool flag=true;

             for(int i=;i<n;i++){

                 if(i==p) continue;

                 if(ss[i].find(ans%cc[i])==ss[i].end()){

                     flag=false;

                     break;

                 }

             }

             if(flag){

                 printf("%lld\n",ans);

                 m--;

             }

             if(!m) break;

         }

         temp++;

     }

 }

 int main(){

     int k,p;

     ll ji,x;

     int t=;

     while(~scanf("%d%d",&n,&m)){

         if(t) printf("\n");

         t=;

         p=-;ji=;

         for(int i=;i<n;i++){

             ss[i].clear();

             scanf("%lld",&cc[i]);

             scanf("%d",&k);

             ji*=k;

             if(p==-||k*cc[p]<(int)ss[p].size()*cc[i]) p=i;

             while(k--){

                 scanf("%lld",&x);

                 ss[i].insert(x);

             }

         }

         if(ji<=) solve1();

         else solve2(p);

     }

     return ;

 }

巧妙的分类解决

巴特西

UVA 11754 Code Feat 中国剩余定理+枚举

Code FeatUVA - 11754

最新文章

热门文章