首页 > 代码库 > 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 __int64 ll 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))==0 void 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; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。