hdu 1573 X问题【扩展中国剩余定理】

扩展中国剩余定理的板子，合并完之后算一下范围内能取几个值即可（记得去掉0）

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=15;

int T,n,m;

long long a[N],b[N],A,B,x,y,d;

bool fl;

void exgcd(long long a,long long b,long long &d,long long &x,long long &y)

{

	if(!b)

	{

		d=a,x=1,y=0;

		return;

	}

	exgcd(b,a%b,d,y,x);

	y-=a/b*x;

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		fl=0;

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

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

			scanf("%d",&a[i]);

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

			scanf("%d",&b[i]);

		A=a[1],B=b[1];

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

		{

			exgcd(A,a[i],d,x,y);

			if((b[i]-B)%d)

			{

				fl=1;

				break;

			}

			x=((b[i]-B)/d*x%(a[i]/d)+(a[i]/d))%(a[i]/d);

			B=B+x*A;

			A=A/d*a[i];

			B%=A;

		}

		if(fl||n<B)

			puts("0");

		else

			printf("%lld\n",(n-B)/A+1-(B==0));

	}

	return 0;

}

巴特西

hdu 1573 X问题【扩展中国剩余定理】

最新文章

热门文章