poj 2891 Strange Way to Express Integers 中国剩余定理非互质情况

xiaoxiao2021-02-28  35

解析:

    传送门

代码:

    

#include<string.h> #include<stdio.h> using namespace std; #define LL long long #define N 100005 LL p[N]; LL r[N]; /** 扩展欧几里得 **/ void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){ if(!b){ d=a,x=1,y=0; }else{ ex_gcd(b,a%b,d,y,x); y-=x*(a/b); } } /** 求t关于p的逆元 **/ LL inv(LL t,LL p){ LL d,x,y; ex_gcd(t,p,d,x,y); return d == 1?(x%p+p)%p:-1; } /**中国剩余定理**/ LL China(int len,LL *a,LL *r){ LL M=a[0],R=r[0],x,y,d; for(int i=1;i<len;i++){ ex_gcd(M,a[i],d,x,y); if((R-r[i])%d!=0) return -1; x=(R-r[i])/d*x%a[i]; R-=x*M; M=M/d*a[i]; R%=M; } return (R%M+M)%M; } int main(){ int k; while(~scanf("%d",&k)){ for(int i=0;i<k;i++){ scanf("%lld %lld",&p[i],&r[i]); } LL res = China(k,p,r); printf("%lld\n",res); } }
转载请注明原文地址: https://www.6miu.com/read-2600241.html

最新回复(0)