[数论][暴力][分段] UVA 11754 Code Feat

之所以写这个题是因为他提供了一种新的解决问题的思路。。两个暴力算法结合起来竟然就不暴力了。。

首先直接暴力枚举每个set里的余数然后解同余方程组可以得到一个Πki复杂度的算法，但是这个在k太大的时候会爆，然后k很大的时候就用了同余方程的另一种暴力解法，找到一个同余方程枚举他的所有解然后去判断其他的等式是否满足。。。这个在k比较大的时候比较快（但是感觉这俩算法组合还是有点看RP
代码基本上都是抄的书上就这。不过调了下LIMIT的范围发现从100到500000都可以过。。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define LL long long
#define limit 5000

LL n,m,x[11],y[11][111],a[11],M,c;
vectore;
setf[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;i0)
            {
                //cout<=n)
            {
                printf("%lld\n",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;iy[0]*x[i])c=i;//ki/xi>kc/xc
        }
        if(t>limit)slove2();//普通枚举，k/x越小越好，这样t*x+yi足够大，很快就能找到
        else slove();//中国剩余定理
        printf("\n");
    }
    return 0;
}