大意:
给出k个模方程组:m mod ai = ri。求m的最小正值。如果不存在这样的m,那么输出-1.
思路:
lcm是广义的,lcm(m1,m2)表示m1,m2序列的最小相等的值。
。。。。。。
算了,不会推导,直接用吧。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int n;
ll a[100005],r[100005];
void gcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){d=a;x=1;y=0;}
else{ gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
ll solve(){
ll M=a[1],R=r[1],x,y,d;
for(int i=2;i<=n;i++){
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(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&r[i]);
printf("%lld\n",solve());
}
return 0;
}
转自: http://blog.csdn.net/zmh964685331/article/details/50527894