HDU3579 Hello Kiki【一元线性同余方程组】

本文主要是介绍HDU3579 Hello Kiki【一元线性同余方程组】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3579

题目大意：

Kiki有X个硬币，她用不同的方式数了N次，每次她把硬币分成大小相等的组，记录每次一组硬币

的个数Mi和数完最后剩余的硬币数Ai。那么问题来了：总共有多少枚硬币？

思路：

典型的一元线性同余方程组X = Ai(mod Mi)求解。题目要求输出最小正整数解，则如果求得同余

方程组的解为0，那么答案就是所有Mi的最小公倍数。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL __int64LL GCD(LL a,LL b)
{if(b == 0)return a;return GCD(b,a%b);
}void ExGCD(LL a,LL b,LL &d, LL &x,LL &y)
{if( !b ){x = 1;y = 0;d = a;}else{ExGCD(b,a%b,d,y,x);y -= x * (a/b);}
}LL A[15],R[15];int main()
{LL a,b,c,d,x0,y0,lcm;int N,M,kase = 0;scanf("%d",&N);while(N--){lcm = 1;bool flag = 1;scanf("%d",&M);for(int i = 1; i <= M; ++i){scanf("%I64d",&A[i]);lcm = lcm / GCD(A[i],lcm) * A[i];}for(int i = 1; i <= M; ++i)scanf("%I64d",&R[i]);printf("Case %d: ",++kase);for(int i = 2; i <= M; ++i){a = A[1];b = A[i];c = R[i] - R[1];ExGCD(a,b,d,x0,y0);if( c%d != 0 ){flag = 0;break;}LL temp = b/d;x0 = (x0*(c/d)%temp + temp) % temp;R[1] = A[1]*x0 + R[1];A[1] = A[1]*(A[i]/d);}if( !flag )printf("-1\n");else{if(R[1] != 0)printf("%I64d\n",R[1]);elseprintf("%I64d\n",lcm);}}return 0;
}

这篇关于HDU3579 Hello Kiki【一元线性同余方程组】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---