• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

模线性方程组

admin

11月 28, 2021

#1303 : 数论六·模线性方程组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Ho:今天我听到一个挺有意思的故事!

小Hi:什么故事啊?

小Ho:说秦末,刘邦的将军韩信带领1500名士兵经历了一场战斗,战死四百余人。韩信为了清点人数让士兵站成三人一排,多出来两人;站成五人一排,多出来四人;站成七人一排,多出来六人。韩信立刻就知道了剩余人数为1049人。

小Hi:韩信点兵嘛,这个故事很有名的。

小Ho:我觉得这里面一定有什么巧妙的计算方法!不然韩信不可能这么快计算出来。

小Hi:那我们不妨将这个故事的数学模型提取出来看看?

小Ho:好!

<小Ho稍微思考了一下>

小Ho:韩信是为了计算的是士兵的人数,那么我们设这个人数为x。三人成排,五人成排,七人成排,即x mod 3, x mod 5, x mod 7。也就是说我们可以列出一组方程:

x mod 3 = 2
x mod 5 = 4
x mod 7 = 6

韩信就是根据这个方程组,解出了x的值。

小Hi:嗯,就是这样!我们将这个方程组推广到一般形式:给定了n组除数m[i]和余数r[i],通过这n组(m[i],r[i])求解一个x,使得x mod m[i] = r[i]。

小Ho:我怎么感觉这个方程组有固定的解法?

小Hi:这个方程组被称为模线性方程组。它确实有固定的解决方法。不过在我告诉你解法之前,你不如先自己想想怎么求解如何?

小Ho:好啊,让我先试试啊!

提示:模线性方程组

输入

第1行:1个正整数, N,2≤N≤1,000。

第2..N+1行:2个正整数, 第i+1行表示第i组m,r,2≤m≤20,000,000,0≤r<m。

计算过程中尽量使用64位整型。

输出

第1行:1个整数,表示满足要求的最小X,若无解输出-1。答案范围在64位整型内。

样例输入
    3
    3 2
    5 3  
    7 2
样例输出
              23
  解线性同余方程,通过不断两两合并方程,最后得解
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define  ll long long
using namespace std;
const int N=1001;
ll m[N],r[N];
int n;
ll gcd(ll a,ll b) {
	return a%b==0 ? b : gcd(b,a%b);
}
void exgcd(ll a,ll b,ll& x,ll& y) {
	if(!b) x=1,y=0;
	else {
		exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y;
		y=tmp-a/b*y;
	}
}
ll solve() {
	ll M=m[1],R=r[1];
	for(int i=2;i<=n;i++) {
		ll d=gcd(M,m[i]);
		ll c=r[i]-R;
		if(c%d) return -1;
		ll k1,k2;
		exgcd(M/d,m[i]/d,k1,k2);
		k1=(c/d*k1) % (m[i]/d);
		R=R+k1*M;
		M=M/d*m[i];
		R%=M;
	}
	while(R<0) R+=M;
	return R;
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld%lld",&m[i],&r[i]);
    printf("%lld",solve());
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注