阅读850 返回首页    go 微软 go Office

HDU1573 一元线性同余方程组

这题很水啊 就是求解一元线性方程组的解 然后问在n的范围内解的个数 很正常的一道题

竟然在输入上 WA了无数次 这个就有点惨了 这个同余方程的解是按照最小公倍数的往上

循环的 然后再注意一下求出的解为0的边界问题就可以了

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0)
    {
        x=1,y=0,d=a;
        return;
    }
    exgcd(b,a%b,d,x,y);
    long long temp=x;
    x=y;
    y=temp-(a/b)*y;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    long long a[15],b[15],m,n,t,a1,r1,a2,r2,c,d,x,y,gc,a0,b0;
    cin>>t;
    while(t--)
    {
        bool flag=0;
        gc=1;
        cin>>n>>m;
        for(int i=0; i<m; i++)
            cin>>b[i],gc=gc/gcd(gc,b[i])*b[i];
        for(int i=0; i<m; i++)
            cin>>a[i];
        r1=a[0];
        a1=b[0];
        for(int i=1; i<m; i++)
        {
            a2=b[i],r2=a[i];
            a0=a1,b0=a2,c=r2-r1;
            exgcd(a0,b0,d,x,y);
            if(c%d)
            {
                flag=1;
                break;
            }
            long long t=b0/d;
            x=(x*(c/d)%t+t)%t;
            r1=r1+a1*x;
            a1=a1*(a2/d);
        }
        if(flag)
        {
            printf("0\n");
            continue;
        }
        long long ans=0;
        if(r1<=n)
            ans=1+(n-r1)/gc;
        if(ans&&r1==0)
            ans--;
        printf("%lld\n",ans);
    }
    return 0;
}


最后更新：2017-04-04 07:03:34

  上一篇：go 2013年关于Linux的5大猜想
  下一篇：go POJ1740