Problem - 7363 (hdu.edu.cn)

参考：2023杭电暑假多校8 题解 3 5 7 10 | JorbanS_JorbanS的博客-CSDN博客

题解：（中国剩余定理 增量法） 

注意验证和特判，此题中 pi 两两互质，可用CRT和增量法，当 pi 不是两两互质时，必须用增量法

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod=1e9+7;
const ll inf=1<<30;
ll T;
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline void print(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1,y=0;return a;}ll xx,yy;ll d=exgcd(b,a%b,xx,yy);x=yy;y=xx-(a/b)*x;return d;
}
ll n,c[N],d[N];
inline ll quickp(__int128 base, ll pow, ll p) {__int128 res = 1;while (pow) {if (pow&1) res=res*base%p;base=base*base%p;pow>>=1;}return res;
}void merge(__int128 &a,__int128 &b,ll c,ll d){//bt=c-a(mod d)ll x,y;ll g=exgcd(b,d,x,y);//bx=g(mod d)if((c-a)%g!=0){a=b=-1;return;}d/=g;//d'll t0=((c-a)/g)%d*x%d;if(t0<0)t0+=d;//最小整数解//t=t0(mod d')a=b*t0+a;b=b*d;
}
void solve(){//增量法解同余方程组n=read();__int128 a=0,b=1;//x mod b = all M=1;for(int i=1;i<=n;i++){d[i]=read();c[i]=read();M*=d[i];if(a!=-1&&b!=-1)merge(a,b,c[i],d[i]);}for(int i=1;i<=n;i++){//求出的不一定是原方程的解验算if(quickp(a,d[i],M)!=c[i])a=-1;}if(a==0)a=M;//特判 mod M 后等于0的情况print(a);printf("\n");
}int main(){T=read();while(T--){solve();}return 0;
}