问题转化
题目给定的m∈[0,a-1],所以$x≡m(\%a)$就等价于$x=ka+m$,m就是余数
下面详细解释转化。
$$x≡m_i(mod\ a_i)$$
$$说明x=k_1a_i+C,\ m_i=k_2a_i+C\ (k_1,k_2∈Z,0≤C<a_i)$$
$$
C=m_i-k_2a_i
$$
$$ 所以x=k_1a_i+(m_i-k_2a_i) $$
$$ x=(k_1-k_2)a_i+m_i $$
$$ 即x\%a_i=m_i\ (x=ka_i+m_i) $$
$$ 总结一下:x≡m_i(mod\ a_i)等价于x\%a_i=m_i\ (x=ka_i+m_i) $$
所以题目问的问题就转化成为:
求x。
数学推导
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<math.h>
typedef long long intt;
intt gcd;
typedef pair<intt,intt> II;
II exgcd(intt a,intt b){
if(b==0){
gcd=a;
return {1,0};
}else{
II temp=exgcd(b,a%b);
return {temp.second,temp.first-a/b*temp.second};
}
}
int main(){
intt n,a1,m1,a2,m2,s,k1,t;
cin>>n;
cin>>a1>>m1;
II temp;
for(intt i=0;i<n-1;i++){
cin>>a2>>m2;
temp=exgcd(a1,a2);//其实应该是-a2,若写+a2就得令y‘=-y,然后再对求出来的y‘取负 但是我们根本用不到y所以无所谓了
if((m2-m1)%gcd!=0){
cout<<"-1"<<endl;
return 0;
}
s=(m2-m1)/gcd;//倍数
k1=temp.first*s;
t=a2/gcd;//k1通=k1特+k*(a2/gcd);
k1=(k1%t+t)%t;//使k1为k1通解中最小的一个非负整数特解 防止溢出
// 之所以再+t是怕k1是负数,使得其即使是负数也能落在0~t-1内
m1=k1*a1+m1;
a1=abs(a1/gcd*a2);//最小公倍数=(a*b/gcd(a,b)) 之所以先除以gcd是怕数太大超出范围;之所以abs是想求一个正的公倍数方便些
m1%=a1;
}
cout<<(m1%a1+a1)%a1<<endl;
return 0;
}
有感而发
真难
能ac震惊我了