HDU 3579 模余方程

2019-04-14 16:08发布

站内文章 / 模拟电子
12770 0 1477
/* HDU 3579 不一定互质情况，神牛公式解析链接：http://yzmduncan.iteye.com/blog/1323599 把推导过程翻译成代码即可... */ #include #include #include using namespace std; typedef long long ll; ll gcd(ll a,ll b){     if(b==0) return a;     return gcd(b,a%b); } ll kzgcd(ll a,ll b,ll&x,ll&y){     if(b==0) {         x=1, y=0;         return a;     }     ll d = kzgcd(b,a%b,x,y);     ll k = y;     y = x - a/b*y;     x = k;     return d; }ll inv(ll a,ll b){ /// 求 a 的逆元 整数最小x     ll x,y;     ll k = kzgcd(a,b,x,y);     if(k!=1) return -1;     return (x%b+b)%b; }bool merge(ll a1,ll n1,ll&a2,ll&n2){     ll d = gcd(n1,n2);     ll c = a2 - a1;     if(c%d) return false;     ll k = inv(n1/d,n2/d)*c/d;     ll a,n;     n = n1/d*n2;     a = (n1*k+a1)%(n1*n2/d);     a2 = a;     n2 = n;     return true; }ll china_reminder(ll k,ll*a,ll*b){ /// 余数，mod数     ll n1=b[1],a1=a[1];     for(ll i=2;i<=k;i++){         ll nn,aa;         nn = b[i], aa = a[i];         if(!merge(a1,n1,aa,nn))             return -1;         n1 = nn;         a1 = aa;     }     return (a1%n1+n1)%n1; }int main(){      ll t,a[1110],b[1100];      int f;      cin>>f;      for(int ca=1;ca<=f;ca++){          cin>>t;          for(ll i=1;i<=t;i++)              cin>>b[i];          for(ll i=1;i<=t;i++)              cin>>a[i];          printf("Case %d: ",ca);          ll sum = china_reminder(t,a,b);          if(!sum){ /// 特判...              sum=1;              for(int i=1;i<=t;i++)                  sum = sum*b[i]/gcd(sum,b[i]);          }          printf("%lld ",sum);      } }

热门文章