HDU1573：X问题（解一元线性同余方程组）

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

题目解析;HDU就是坑，就是因为n,m定义成了__int64就WAY，改成int就A了，无语。

这题就是求解一元线性同余方程组的解满组小于正整数n的数目。最小正整数的解为X=(X*(c/d)%t+t)%t;
  X=a1*X+r1;其中X为扩展欧几里得解出来的特解，这m个方程组的循环区间为lcm(a1,a2,a3...am),
所以答案为(n-X)/lcm+1;

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

__int64 a,b,c,d;

__int64 X,Y;

__int64 gcd(__int64 A,__int64 B)

{

    return B==?A:gcd(B,A%B);

}

void extend(__int64 A,__int64 B,__int64 &d,__int64 &x1,__int64 &y1)

{

    if(B==)

    {

        x1=;

        y1=;

        d=A;

        return ;

    }

    extend(B,A%B,d,x1,y1);

    __int64 temp=x1;

    x1=y1;

    y1=temp-(A/B)*y1;

    return ;

}

int main()

{

    __int64 S[],E[];

    __int64 a1,r1,a2,r2,Lcm;

    __int64 T;

    int n,m;

    scanf("%I64d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        Lcm=;

        for(int i=; i<=m; i++)

        {

            scanf("%I64d",&S[i]);

            Lcm=Lcm/gcd(Lcm,S[i])*S[i];//在一定程度上可以防止爆类型(Lcm*S[i]/gcd())

        }

        for(int i=; i<=m; i++)

        {

            scanf("%I64d",&E[i]);

        }

        bool ifhave=true;

        a1=S[],r1=E[];

        for(__int64 i=; i<=m; i++)

        {

            a2=S[i],r2=E[i];

            a=a1;

            b=a2;

            c=r2-r1;

            extend(a,b,d,X,Y);

            if(c%d)

            {

                ifhave=false;

                break;

            }

            __int64 t=b/d;

            X=(X*(c/d)%t+t)%t;

            X=a1*X+r1;

            a1=a1*(a2/d);

            r1=X;

        }

        __int64 ans=;

        if(!ifhave)

        {

            printf("0\n");

            continue;

        }

        if(r1<=n) ans=+(n-r1)/Lcm;

        if(r1==&&ans)

            ans--;

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

    }

    return  ;

}