信息学奥赛一本通 1635：【例 5】Strange Way to Express Integers

【题目链接】

ybt 1635：【例 5】Strange Way to Express Integers
LOJ #10213. 「一本通 6.4 例 5」Strange Way to Express Integers

【题目考点】

1. 扩展中国剩余定理

相关知识见：洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

【解题思路】

本题没有指明同余方程组的模数m 1 , m 2 , . . . , m n m_1, m_2, ..., m_nm1​,m2​,...,mn​互质，因此不能使用中国剩余定理，需要使用扩展中国剩余定理。
本题是扩展中国剩余定理的模板题，要求对多组数据求解。
相关知识及解题方法见：洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

【题解代码】

解法1：扩展中国剩余定理

#include<bits/stdc++.h>usingnamespacestd;#defineN100005#defineMOD(a,b)(((a)%(b)+(b))%(b))typedeflonglongLL;voidexgcd(LL a,LL b,LL&x,LL&y,LL&g){if(b==0){x=1,y=0,g=a;return;}exgcd(b,a%b,y,x,g);y-=a/b*x;}LLexCRT(LL*a,LL*m,LL n)//x≡a[i] (mod m[i]){LL ca=a[1],cm=m[1],x,y,g,lcm;for(inti=2;i<=n;++i){exgcd(cm,m[i],x,y,g);if((a[i]-ca)%g!=0)return-1;//无解时返回-1lcm=cm/g*m[i];//lcm(cm, m[i])ca=MOD(MOD((__int128)(a[i]-ca)/g*x,m[i]/g)*cm+ca,lcm);//此处不能使用函数mod，因为会把int128类型转为LL类型，有精度丢失cm=lcm;}returnca;}intmain(){LL a[N],m[N],n;while(cin>>n){for(inti=1;i<=n;++i)cin>>m[i]>>a[i];cout<<exCRT(a,m,n)<<'\n';}return0;}