型線形方程式グループ-非互質中国残留定理(2012/5/18に更新)
KIDxの問題解決報告はこのテーマに必要な知識があります.モデル解き式http://972169909-qq-com.iteye.com/blog/1104538以下のオリジナル転載は作者(KIDx)と文章の住所を指定してください.
http://972169909-qq-com.iteye.com/blog/1266328
問題の説明:bi,niの値を提供して、しかもn 1,n 2,n 3,…,niの2つの間は必ずしも互いに質的ではなくて、Resの値を求めますか?解:方程式を統合する方法を採用しています.ここでは、第一の第二の方程式を統合する例として、上図の前の2つの方程式から得られる(k 1、k 2をある整数とする)を説明する.
タイトル:hdu 1573 X問題【以下、コードが与えられました】別のオススメです.hdu 3579 Hello Kiki:http://acm.hdu.edu.cn/showproblem.php?pid=1573
http://972169909-qq-com.iteye.com/blog/1266328
問題の説明:bi,niの値を提供して、しかもn 1,n 2,n 3,…,niの2つの間は必ずしも互いに質的ではなくて、Resの値を求めますか?解:方程式を統合する方法を採用しています.ここでは、第一の第二の方程式を統合する例として、上図の前の2つの方程式から得られる(k 1、k 2をある整数とする)を説明する.
タイトル:hdu 1573 X問題【以下、コードが与えられました】別のオススメです.hdu 3579 Hello Kiki:http://acm.hdu.edu.cn/showproblem.php?pid=1573
#include <iostream>
using namespace std;
#define LL __int64
#define M 10
int N;
LL Egcd (LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
LL d, tp;
d = Egcd (b, a%b, x, y);
tp = x;
x = y;
y = tp - a/b*y;
return d;
}
LL CRT2 (LL b[], LL n[], int num)
{
int i;
bool flag = false;
LL n1 = n[0], n2, b1 = b[0], b2, bb, d, t, k, x, y;
for (i = 1; i < num; i++)
{
n2 = n[i], b2 = b[i];
bb = b2 - b1;
d = Egcd (n1, n2, x, y);
if (bb % d) // k1
{
flag = true;
break;
}
k = bb / d * x; // k1【 】
t = n2 / d;
if (t < 0) t = -t;
k = (k % t + t) % t; // K`
b1 = b1 + n1*k;
n1 = n1 / d * n2;
}
if (flag)
return 0; //
/****************** ******************/
if (b1 == 0) // 0, ,
b1 = n1; //n1 ni ,
/****************** ******************/
if (b1 > N)
return 0;
return (N-b1)/n1+1; // :b1, b1+n1, b1+2n1,..., b1+xni...
}
int main()
{
int t, num, i, cc = 1;
LL b[M], n[M];
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &N, &num);
for (i = 0; i < num; i++)
scanf ("%I64d", n+i);
for (i = 0; i < num; i++)
scanf ("%I64d", b+i);
printf ("%I64d
", CRT2 (b, n, num));
}
return 0;
}