首页 > 代码库 > POJ 2891 Strange Way to Express Integers 中国剩余定理
POJ 2891 Strange Way to Express Integers 中国剩余定理
裸题,上模版,,嘿嘿
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<queue> #include<vector> #include<map> using namespace std; #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 work(ll l, ll r, ll *m, ll *a){ //下标[l,r] 方程x%m=a; ll lcm = 1; for(ll i = l; i <= r; i++)lcm = lcm/gcd(lcm,m[i])*m[i]; for(ll i = l+1; i <= r; i++) { ll A = m[l], B = m[i], d, k1, k2, c = a[i]-a[l]; extend_gcd(A,B,d,k1,k2); if(c%d)return -1; ll mod = m[i]/d; ll K = ((k1*c/d)%mod+mod)%mod; a[l] = m[l]*K + a[l]; m[l] = m[l]*m[i]/d; } if(a[l]==0)return lcm; return a[l]; } #define N 10005 ll n[N],b[N],len; int main(){ ll len; while(cin>>len){ for(ll i = 1; i <= len; i++) cin>>n[i]>>b[i]; cout<<work(1,len,n,b)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。