POJ2891:Strange Way to Express Integers(解一元线性同余方程组)

写一下自己的理解,下面附上转载的:
若a==b(modk);//这里的==指的是同余,我用=表示相等(a%k=b)
a-b=kt(t为整数)
以前理解的错误思想:
以前认为上面的形式+(a-tb=k)也是成立的,今天一想随便就能举出一个反例11==5(mod3)
同样是求这个东西。。
X mod m1=r1
X mod m2=r2
...
...
...
X mod mn=rn 首先,我们看两个式子的情况
X mod m1=r1……………………………………………………………(1)
X mod m2=r2……………………………………………………………(2)
则有
X=m1*k1+r1………………………………………………………………(*)
X=m2*k2+r2
那么 m1*k1+r1=m2*k2+r2
整理,得
m1*k1-m2*k2=r2-r1
令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成
ax+by=m
熟悉吧? 此时,因为GCD(a,b)=1不一定成立,GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立,则!!!方程无解!!!。(即合并的这两个方程组不可能相等,即没有同解X)
否则,继续往下。 解出(x,y),将k1=x反代回(*),得到X。//解出的一组特解(x,y)代入是(1)(2)两个方程所得X是相等的。
于是X就是这两个方程的一个特解,通解就是 X'=X+k*LCM(m1,m2)//(特解为X=x*(c/d)*m1+r1;同解X'=X+(m2/d)*m1*k,=X+lcm(m1,m2)*k)
这个式子再一变形,得 X' mod LCM(m1,m2)=X
这个方程一出来,说明我们实现了(1)(2)两个方程的合并。 转载: /**********************一般模线性方程组***********************/ 同样是求这个东西。。
X mod m1=r1
X mod m2=r2
...
...
...
X mod mn=rn 首先,我们看两个式子的情况
X mod m1=r1……………………………………………………………()
X mod m2=r2……………………………………………………………()
则有
X=m1*k1+r1………………………………………………………………(*)
X=m2*k2+r2
那么 m1*k1+r1=m2*k2+r2
整理,得
m1*k1-m2*k2=r2-r1
令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成
ax+by=m
熟悉吧? 此时,因为GCD(a,b)=1不一定成立,GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立,则!!!方程无解!!!。
否则,继续往下。 解出(x,y),将k1=x反代回(*),得到X。
于是X就是这两个方程的一个特解,通解就是 X'=X+k*LCM(m1,m2)
这个式子再一变形,得 X' mod LCM(m1,m2)=X
这个方程一出来,说明我们实现了()()两个方程的合并。
令 M=LCM(m1,m2),R=r2-r1
就可将合并后的方程记为 X mod M = R。 然后,扩展到n个方程。
用合并后的方程再来和其他的方程按这样的方式进行合并,最后就能只剩下一个方程 X mod M=R,其中 M=LCM(m1,m2,...,mn)。
那么,X便是原模线性方程组的一个特解,通解为 X'=X+k*M。 如果,要得到X的最小正整数解,就还是原来那个方法: X%=M;
if (X<) X+=M; 这么一来~~大功告成~~

PS:2015.1.21题目解析:这个算法我没有搞懂,以后只能靠模版了,,囧!!!(希望看完中国剩余定理后能对这里有一个重新的认识)

PS:1.22终于完全搞懂了,好开心,重新解释一下。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
long long a,b,c,n,d;
long long X,Y;
void extend(long long A,long long B,long long &d,long long &x1,long long &y1)
{
if(B==)//犯了一个低级失误如果写成long long d的话函数的值传回到主函数
{
x1=;
y1=;
d=A;
return ;
}
extend(B,A%B,d,x1,y1);
long long temp=x1;
x1=y1;
y1=temp-(A/B)*y1;
return ;
}
int main()
{
long long a1,r1,a2,r2,i,j;
while(scanf("%lld",&n)!=EOF)
{
bool ifhave=true;
scanf("%lld%lld",&a1,&r1);
for(i=; i<=n; i++)
{
scanf("%lld%lld",&a2,&r2);
a=a1;
b=a2;
c=r2-r1;
extend(a,b,d,X,Y);
if(c%d)
{
ifhave=false;
break;
}
long long t=b/d;
X=(X*(c/d)%t+t)%t;//最小解
X=a1*X+r1;//带入原方程求出一个特解X,这个特解同时满足合并的两个方程组,那么通解为X‘=X+(a2/d)*a1*k,即X'=X+lcm(a1,a2)*k;->X'mod lcm(a1,a2)=X;
//printf("X===%lld\n",X);
a1=a1*(a2/d);// 即lcm(a1,a2)
r1=X; //上面证明即为两个方程组的合并
}
for(j=i+; j<=n; j++)
{
scanf("%lld%lld",&a2,&r2);
}
if(!ifhave)
{
printf("-1\n");
continue;
}
printf("%lld\n",X);
}
return ;
}
上一篇:HDU1573:X问题(解一元线性同余方程组)


下一篇:AcWing 204. 表达整数的奇怪方式 (线性同余方程组)打卡