poj2891 Strange Way to Express Integers 扩张欧几里德的应用

poj2891 Strange Way to Express Integers 扩展欧几里德的应用

刚开始数论，还不知道中国余数定理这东西，后来看了看，本题不互素（互质）所以不能直接套中国余数定理，要两两合并公式，看了网上很多题解，基础真心很差结果都没看懂，但是终于看到了一篇让我这么没资质的人懂了

转一下他的分析

模不互素，不能直接用中国剩余定理，只能每次求2组方程，然后通过他们的lcm求出最后符合左右方程组的解。例如有下面2条同余方程 x ≡ 3 (mod 4)，x ≡ 5 (mod 6)。

x = 3 + 4j≡ 5 (mod 6)两边同时减去3

4j ≡ 2 (mod 6)两边同时除于 gcd(4,2,6)

2j ≡ 1 (mod 3)因为2关于3同余1的逆是2

j ≡ 2 (mod 3)

j = 2 + 3k

x = 3 + 4(2 + 3k)这步就是r1 = a1 * x + r1
x = 11 + 12k，m = lcm(m1,m2)

x ≡ 11 (mod 12)

他举了具体数字看起来就好懂多了

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long
#define LL __int64
#define eps 1e-8
const ll INF=9999999999999;

using namespace std;

#define M 400000100

#define inf 0xfffffff

//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

//vector<int>G[30012];

LL x,y,t;

LL extgcd(LL a,LL b)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		LL temp=extgcd(b,a%b);
		t=x;
		x=y;
		y=t-a/b*y;
		return temp;
	}
}

int main(void)
{
	int n;
	while(cin>>n)
	{
		bool flag=false;
		LL a,r;
		cin>>a>>r;
		for(int i=0;i<n-1;i++)
		{
			LL a1,r1; 
			cin>>a1>>r1;
			if(flag)
				continue;
			LL d=r1-r;
			LL gcd=extgcd(a,a1);
			if(d%gcd!=0)
			{
				flag=true;
				continue;
			}
			LL temp=a1/gcd;
			x=(d/gcd*x%temp+temp)%temp;//直接取余的话，如果求出的gcd值为负数，那就会得到个负数，取余的时候要写成这样子
			r=a*x+r;
			a=a*a1/gcd;
		}
		if(flag)
			puts("-1");
		else
			cout<<r<<endl;
	}
}

poj2891 Strange Way to Express Integers 扩张欧几里德的应用

相关推荐