本文主要是介绍HDU1573 X问题【一元线性同余方程组】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1573
题目大意：
求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2],
…, X mod a[i] = b[i], … (0 < a[i] <= 10)。
思路：
先求出数组b[]中所有数的最小公倍数lcm，再求解出该一元线性同余方程组在lcm范围内的解为a，题目要
求解x是小于等于N的正整数，则可列不等式：a + lcm * x <= N。那么，如果a = 0，则答案为x-1，如果
a != 0，则答案为x。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;__int64 GCD(__int64 a,__int64 b)
{if(b == 0)return a;elsereturn GCD(b,a%b);
}void ExGCD(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y)
{if( !b ){x = 1;y = 0;d = a;}else{ExGCD(b,a%b,d,y,x);y -= x * (a/b);}
}__int64 A[15],B[15];int main()
{int T,N,M;__int64 a,b,c,d,x0,y0,lcm;cin >> T;while(T--){cin >> N >> M;bool flag = 1;lcm = 1;for(int i = 1; i <= M; ++i){cin >> A[i];lcm = lcm / GCD(lcm,A[i]) * A[i];}for(int i = 1; i <= M; ++i)cin >> B[i];for(int i = 2; i <= M; ++i){a = A[1];b = A[i];c = B[i] - B[1];ExGCD(a,b,d,x0,y0);if(c % d != 0){flag = 0;break;}__int64 temp = b / d;x0 = (x0*(c/d)%temp + temp) % temp;B[1] = A[1] * x0 + B[1];A[1] = A[1] * (A[i]/d);}if( !flag ){cout << "0" << endl;continue;}__int64 Ans = 0;if(B[1] <= N)Ans = 1 + (N - B[1])/lcm;if(Ans && B[1] == 0)Ans--;cout << Ans << endl;}return 0;
}
这篇关于HDU1573 X问题【一元线性同余方程组】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
