HDU 1573 CRT

CRT模板题
/** @Date    : 2017-09-15 13:52:21

  * @FileName: HDU 1573 CRT EXGCD.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

LL mod;

LL a[11];

LL b[11];

LL exgcd(LL a, LL b, LL &x, LL &y)

{

	LL d = a;

	if(b == 0)

		x = 1, y = 0;

	else

	{

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

		y -= (a / b) * x;

	}

	return d;

}

LL md(LL x,LL y)

{

	LL res = x % y;

	if(res <= 0)

		res = res + y;

	return res;

}

int main()

{

	int T;

	cin >> T;

	while(T--)

	{

		LL n, m;

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

		for(int i = 0; i < m; i++) scanf("%d", a + i);

		for(int j = 0; j < m; j++) scanf("%d", b + j);

		LL rem, mod;

		LL x, y;

		LL ans = 0;

		int flag = 0;

		rem = b[0], mod = a[0];

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

		{

			LL c = b[i] - rem;

			LL g = __gcd(a[i], mod);

			if(c % g!= 0)

				flag = 1;

			else

			{

				exgcd(mod, a[i], x, y);

				LL tmp = a[i] / g;

				//x = (c / g * x % tmp + tmp) % tmp;// m1x1+m2x2 = c

				x = md(c / g * x, tmp);//x =

				rem = md(rem + mod * x, mod / g * a[i]);

				//rem = mod * x + rem;//ri + mixi

				mod = mod / __gcd(mod, a[i]) * a[i];//LCM(m1, m2);

				//y mod lcm(m1,m2) = x

			}

		}

		//cout << rem <<"~" << mod << endl;

		if(flag || n < rem)

			printf("0\n");

		else printf("%lld\n", (n - rem) / mod + 1);

	}

    return 0;

}//shi·ne
巴特西

HDU 1573 CRT

最新文章

热门文章
