题解 | #分糖果#

首先题意为求同余线性方程x%pi=ri

首先考虑两个方程x%a1=m1,x%a2=m2;

化简x=k1a1+m1,x=k2a2+m2;

k1a1-k2a2=m2-m1;

由裴蜀定理可知该方程有整数解的条件是 （m2-m1）%（gcd(a1,a2)）==0

同时可以由扩展欧几里得得到k1和k2

同时这个方程的通解是k1=k1+ka2/gcd(a1,a2), k2=k2+ka1/gcd(a1,a2);

因此 x=k1a1+m1=k1a1+m1+k*lcm(a1,a2);

设k1*a1+m1为m, lcm(a1,a2)为a所以得到新的方程x=ka+m;

与之前 两个方程形式一样所以可以把两个方程化为一个方程，重复这个过程可以把题目的n个方程组化为1个且可知这个方程的m就是原n个方程的解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	int flag=1;
	int a1,m1,a2,m2;
	cin>>a1>>m1;
	for(int i=2;i<=n;i++){
		cin>>a2>>m2;
		int x,y;
		int d=exgcd(a1,a2,x,y);
		if((m2-m1)%d!=0){
			flag=0;
			break;
		}
		x*=(m2-m1)/d;
		int t=abs(a2/d);
		x=(x%(t)+t)%(t);
		m1=x*a1+m1;
		a1=abs(a1/d*a2);
	}
	if(flag){
		cout<<m1;
	}else cout<<-1;
	return 0;
}