solved:3
rank:

C.Congruences

题意:对于每组数据给定M个pi和qi,pi为两两不同的质数,N为所有pi的积,问是否存在最小的正整数x使得 x^pi在模N的意义下与qi同余可以推出x^pi在模pi的意义下与qi同余在模N的意义下与qi同余,如果存在输出x,否则输出-1;
显然x^pi在模N的意义下与qi同余可以推出x^pi 在模pi的意义下与qi同余,此外,由于pi为质数,故由费马小定理可得,x^pi在模pi的意义下与x同余,因此原问题可转化为给定M个pi和qi,问是否存在最小的正整数x使得x在模pi的意义下与qi同余,用中国剩余定理计算即可,注意要开int128;
又因x^pi在模N的意义下与qi同余可以推出x^pi在模pi的意义下与qi同余的逆命题不成立,故在算出来结果后还需对每一组pi和qi判断是否成立;
`#include<bits/stdc++.h>

define ll long long

using namespace std;
typedef __int128_t int128;
ll read(){
char ch=getchar();ll x=0,f=1;
while(ch<'0'||ch>'9'){if(ch'-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x10+ch-'0'; ch=getchar();}
return xf;
}
const int maxn=1000000+11;
ll T,M,N,x;
ll p[maxn],q[maxn];
ll p2[maxn],q2[maxn],t[maxn];
ll quickpow(int128 a,ll b,ll Mod){
ll ret=1;
while(b){
if(b&1)ret=(int128)reta%Mod;
a=(int128)aa%Mod;
b>>=1;
}
return ret;
}
int main(){
T=read();
while(T--){
M=read();
N=1;x=0;
for(int i=1;i<=M;i++){
p[i]=read();q[i]=read();
N=Np[i];q2[i]=q[i]%p[i];
}
for(int i=1;i<=M;i++)p2[i]=N/p[i];
for(int i=1;i<=M;i++){
t[i]=quickpow(p2[i],p[i]-2,p[i]);
}
for(int i=1;i<=M;i++){
x=(x+(((int128)q2[i]p2[i])%N*t[i])%N)%N;
}
x=(x%N+N)%N;
if(x0)x=N;
bool flag=true;
for(int i=1;i<=M;i++){
if(quickpow((int128)x,p[i],N)!=q[i]){
cout<<"-1"<<endl;
flag=false;
break;
}
}
if(flag){
cout<<x<<endl;
}
}
return 0;
}
`