http://acm.hdu.edu.cn/showproblem.php?pid=1573

不互质的中国剩余定理,一开始还只以为是中国剩余定理了,长时间没做过了

翻笔记,没找到,搜一搜,点开发现是两个月前的自己的blog,汗一个

数据有trick,多谢wr大牛

#include <cstdio>
typedef long long lld;
#define maxn 12
int r[maxn];
int m[maxn];

lld gcd(lld a,lld b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
lld x, y, t;
lld egcd(lld a, lld b)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        lld e = egcd(b, a % b);
        t = x; x = y; y = t - a / b * y;
        return e;
    }
}

lld exChnRnd(int len)
{
    int i;
    lld d,c,t,mm=m[0],rr=r[0];
    for(i=1;i<len;i++)
    {
        d=egcd(mm,m[i]);
        c=r[i]-rr;
        if(c%d)
            return -1;
        t=m[i]/d;
        x=(c/d*x%t+t)%t;
        rr=mm*x+rr;
        mm=mm*m[i]/d;
    }
        return rr;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int n,i,M;
    lld t,sum;
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&M,&n);
        sum=1;
        for(i=0;i<n;i++)
        {
            scanf("%d",m+i);
            sum=sum/gcd(sum,m[i])*m[i];
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",r+i);
            r[i]%=m[i];
        }
        t=exChnRnd(n);
        //printf("t:%lld\n",t);
        //printf("sum:%lld\n",sum);
        if(t==-1)
        {
            printf("0\n");
            continue;
        }
        i=0;
        if(t<=M) i=1+(M-t)/sum;
        if(t==0&&i)//这里...
            --i;
        printf("%d\n",i);
    }
}