HDU 3579 Hello Kiki 中国剩余定理(合并方程

发布时间:2017-7-9 7:26:32编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 3579 Hello Kiki 中国剩余定理(合并方程 ",主要涉及到HDU 3579 Hello Kiki 中国剩余定理(合并方程 方面的内容,对于HDU 3579 Hello Kiki 中国剩余定理(合并方程 感兴趣的同学可以参考一下。

题意:

给定方程

res % 14 = 5

res % 57 = 56

求res

中国剩余定理裸题

#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>#include<math.h>#include<set>#include<queue>#include<vector>using namespace std;#define N 10005#define ll __int64ll gcd(ll a, ll b) {	return b == 0 ? a : gcd(b, a%b);}//求一组解(x,y)使得 ax+by = gcd(a,b), 且|x|+|y|最小(注意求出的 x,y 可能为0或负数)。//以下代码中d = gcd(a,b)//能够扩展成求等式 ax+by = c,但c必须是d的倍数才有解,即 (c%gcd(a,b))==0void extend_gcd (ll a , ll b , ll& d, ll &x , ll &y) {  	if(!b){d = a; x = 1; y = 0;}	else {extend_gcd(b, a%b, d, y, x); y-=x*(a/b);}}ll inv(ll a, ll n) { //计算%n下 a的逆。假设不存在逆return -1;	ll d, x, y;	extend_gcd(a, n, d, x, y);	return d == 1 ? (x+n)%n : -1;}ll n[N],b[N],len,lcm;ll work(){	for(ll i = 2; i <= len; i++) {		ll A = n[1], B = n[i], d, k1, k2, c = b[i]-b[1];		extend_gcd(A,B,d,k1,k2);		if(c%d)return -1;		ll mod = n[i]/d;		ll K = ((k1*(b[i]-b[1])/d)%mod+mod)%mod;		b[1] = n[1]*K + b[1];		n[1] = n[1]*n[i]/d;	}	if(b[1]==0)return lcm;	return b[1];}int main(){	ll i,T,Cas=1;cin>>T;	while(T--){		cin>>len;		lcm = 1;		for(i=1;i<=len;i++) {			cin>>n[i];			lcm = lcm / gcd(lcm,n[i]) * n[i];		}		for(i=1;i<=len;i++)cin>>b[i];		cout<<"Case "<<Cas++<<": ";		cout<<work()<<endl;	}


上一篇:Thrift总结(二)创建RPC服务
下一篇:linux中查看nginx、apache、php、mysql配置文件路径的方法

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款