题目链接：

http://poj.org/problem?id=2891（裸题）
像这种
$X % 8 = 7$
$X % 11 = 9$
求 $X$ 等于多少？

阔以写成：
$X = 8 k_{1} + 7$
$X = 11 k_{2} + 9$
所以： $8 k_{1} + 7 = 11 k_{2} + 9$
即： $8 k_{1} - 11 k_{2} = 2$
这个式子我们就阔以用 $e x g c d$ 求出 $k 1$
要注意的是：
$e x g c d$ 求的是 $8 k_{1} + 11 k_{2} = g c d (8, 11)$ 的解
也就是 $8 k_{1} + 11 k_{2} = 1$ 的解： $k_{1} = - 4, k_{2} = 3$

而我们这里

①：

中间是减号，但是没有关系，阔以看成 $8 k_{1} + 11 (- k_{2}) = 1$ ，求出来的 $k_{2}$ 添个负号就行了，也就是说 $8 k_{1} - 11 k_{2} = 1$ 的解为： $k_{1} = - 4, k_{2} = - 3$

②：

我们的这里的 $2$ 是 $g c d (8, 11)$ 的两倍，那么我们直接在原答案上乘个 $2$ 倍就行了，也就是说
$8 k_{1} - 11 k_{2} = 2$ 的解为： $k_{1} = - 8, k_{2} = - 6$

③：

那万一是 $g c d$ 的 $1.5$ 倍怎么办？那 $k_{1} = - 6, k_{2} = - 4.5$ 么？这样求出来的就不是整数了，而我们要的是整数解，所以：方程的右边不是 $g c d$ 的整数倍时：无解

好现在我们求出了 $k_{1}, k_{2}$ ，随便选一个代回去就能得到 $X$ ，(一般都选 $k_{1}$ ，因为 $k_{2}$ 说不定还要添个负号，挺麻烦的)
那么 $X = 8 * (- 8) + 7 = - 57$
为啥是个负的喃？
因为， $k_{1}, k_{2}$ 是一组解，阔以随便选，只是要满足 $8 k_{1} - 11 k_{2} = 2$ 那就随便选
而且阔以发现 $k_{1}$ 只能加减 $\frac{l c m (8, 11)}{11}$ 这么多， $k_{2}$ 只能加减 $\frac{l c m (8, 11)}{8}$ 这么多
因此，假如某一次求得的 $k_{1}$ 太大了，继续下一步操作就有阔能爆long long，因此阔以先 $%$ 一个 $\frac{l c m (8, 11)}{11}$ 让他变小
而且随便代一个 $k_{1}$ 就是一个 $X$ ，这不就是通解特解的概念么？
那么 $X$ 就有一个通解： $X = k * \frac{l c m (8, 11)}{11} + X_{0}$
$X_{0} 就是随便代一个 k_{1} 得到的特解$
比如我取 $k_{1} = - 6, 那么 X_{0} = - 57$
通解就是 $X = k * 8 - 57$
阔步阔以看成是 $X % 8 = - 57$
诶~把上面两个方程化成了一个方程
同余方程就是这样，两个两个的化，最后只剩一个方程，再取合适的 $k 1$ 就行了

/*poj2891*/
#include"iostream"
using namespace std;
typedef  long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y,LL c)
{
    if (b == 0)
    {
        x = c;
        y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, x, y,c);
    LL t = x;
    x = y;
    y = t - a / b * y;
    return d;
}
int main()
{
    LL N;
    while(cin>>N)
    {
        LL A,R,a,r,res;
        LL x,y;
        int flag=0;
        cin>>A>>R;
        for(int i=2;i<=N;i++)
        {
            cin>>a>>r;
            LL d=exgcd(A,a,x,y,1);
            if((r-R)%d)flag=1;

            LL lcm=A/d*a;
            x*=(r-R)/d;
            x%=lcm/A;//这里就是x太大，继续下一步计算有可能爆long long的地方
            res=A*x+R;
            res=(res%lcm+lcm)%lcm;
            A=lcm,R=res;
        }
        if(flag)cout<<-1<<endl;
        else cout<<res<<endl;
    }
}

为了以后方便使用，我用pair把封装起来了

#include"iostream"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const LL inf=1e15;
LL exgcd(LL a, LL b, LL &x, LL &y,LL c)
{
	if (b == 0)
	{
		x = c;
		y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, x, y,c);
	LL t = x;
	x = y;
	y = t - a / b * y;
	return d;
}
pair<LL,LL> solve(pair<LL,LL> p1,pair<LL,LL> p2)//计算两个同余方程组，返回的也是pair
{
	LL m1=p1.first,r1=p1.second;
	LL m2=p2.first,r2=p2.second;
	LL x,y;
	LL d=exgcd(m1,m2,x,y,1);
	if((r2-r1)%d)return make_pair(inf,inf);//无解情况
	LL lcm=m1/d*m2;
	x*=(r2-r1)/d;
	x%=lcm/m1;//x可能太大，模一下
	LL res=m1*x+r1;
	res=(res%lcm+lcm)%lcm;
	return make_pair(lcm,res); 

}
pair<LL,LL>a[maxn];//用pair封装，first是模数，second是余数
int main()
{
	int N;
	while(cin>>N)
	{
		for(int i=1; i<=N; i++)
		{
			LL t1,t2;
			cin>>t1>>t2;
			a[i]=make_pair(t1,t2);
		}
		pair<LL,LL>res=a[1];
		int flag=0;
		for(int i=2;i<=N;i++)
		{
			res=solve(res,a[i]);
			if(res.first==inf)
			{
				flag=1;
				break;
			}
		}
		if(flag)cout<<-1<<endl;
		else cout<<res.second<<endl;
	}
}

poj 2891 同余方程

文章目录

题目链接：

①：

②：

③：

为了以后方便使用，我用pair把封装起来了