概述
*假设同余方程组
* x=a[1](mod m[1])
* x=a[2](mod m[2])* .
* .
* .
* x=a[r](mod m[r])
*求解非负正整数解x
*思路：对于模线性方程组，在意进行方程组的合并，求出合并后的方程的解，这样就可以得出方程组的解，不管这样的方程有多少个，通过两两合并求得所有的解；因此，我们求*解的时候只要通过两个方程就可以了
* x=a[1](mod m[1])
* x=a[2](mod m[2])*令mm=[m1,m2]
*首先，方程有解的充要条件是(m1,m2)|(b1-b2)，此时方程只有一个小于mm的非负整数解，利用扩展欧几里得算法就可以求出
*式1等价于x=a[1]+m[1]*y1;
*式2等价于x=a[2]+m[2]*y2;
*联立得到a[1]+m[1]*y1=a[2]+m[2]*y2，即m[2]*y2-m[1]*y1=b1-b2
*通过解一元线性方程可求解，再通过两两合并的思想来进行下一个方程
poj2891
题目连接：http://poj.org/problem?id=2891
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
x=1;
y=0;
d=a;
return ;
}
ex_gcd(b,a%b,d,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
int main()
{
ll k;
ll a1,r1,a2,r2;
ll a,b,c,d;
ll x,y;
bool flag;
while(cin>>k)
{
flag=true;
cin>>a1>>r1;
for(ll i=1; i<k; i++)
{
cin>>a2>>r2;
a=a1,b=a2,c=r2-r1;
ex_gcd(a,b,d,x,y);
if(c%d!=0)
{
flag=0;
}
a=a/d,b=b/d,c=c/d;
x=(x*c%b+b)%b;
r1+=a1*x;
a1*=a2/d;
}
if(!flag)
{
cout<<-1<<endl;
continue;
}
cout<<r1<<endl;
}
return 0;
}
hdu1573
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1573
*题意：满足同余方程组的x<m的个数
*
*思想：判断同余方程组在某个范围内的解的个数，在同余问题的基础上增加一个解不等式的过程，
*令A数组中所有数的最小公倍数是lcm，方程在lcm范围内的非负整数的解是a，则有a+lcm*x<=m,若a！=0，
*那么解的的x就是所求的个数，否则x-1就是解
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll ex_gcd(ll a,ll b,ll &x,ll&y)
{
if(!b)
{
x=1;
y=0;
return a;
}
ll r=ex_gcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return r;
}
int rr[15],aa[15];
int main()
{
ll t;
ll n,m;
ll lcm;//最小公倍数
ll a,b,c,d;
ll x,y;
bool flag;
cin>>t;
for(int k=1; k<=t; k++)
{
cin>>m>>n;
lcm=1;
flag=true;
for(int i=1; i<=n; i++)
{
cin>>aa[i];
lcm=lcm/gcd(lcm,aa[i])*aa[i];
}
for(int i=1; i<=n; i++)
cin>>rr[i];
for(int i=2; i<=n; i++)
{
a=aa[1],b=aa[i],c=rr[i]-rr[1];
d=ex_gcd(a,b,x,y);
if(c%d!=0)
{
flag=false;
break;
}
a=a/d,b=b/d,c=c/d;
x=(x*c%b+b)%b;
rr[1]+=aa[1]*x;
aa[1]*=aa[i]/d;
}
if(flag==false)
{
cout<<"0"<<endl;
//continue;
}
ll ans=0;
if(rr[1]<=m)
ans=1+(m-rr[1])/lcm;
if(ans&&!rr[1])
ans--;
cout<<ans<<endl;
}
return 520;
}
hdu3579
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3579* 对于一个x，如果把x等分成n组，此时根据n的变化，可以得到不同的Mi和Ai，在这儿Mi表示每一次等
*分时一组的硬币数量，Ai表示等分后的余数
*
* 题意：给出n组Mi和Ai，求出x
*
* 思路：同余方程组的应用
*
* 这是典型的同余方程组的应用，但是要注意一点，题目要求输出最小的正整数解，如果所求的同余
*方程组的解为0，那么就应当输出Mi的最小公倍数
*
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll ex_gcd(ll a,ll b,ll &x,ll&y)
{
if(!b)
{
x=1;
y=0;
return a;
}
ll r=ex_gcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return r;
}
int rr[15],aa[15];
int main()
{
ll t;
ll n;
ll lcm;//最小公倍数
ll a,b,c,d;
ll x,y;
bool flag;
cin>>t;
for(int k=1; k<=t; k++)
{
cin>>n;
lcm=1;
flag=true;
for(int i=1; i<=n; i++)
{
cin>>aa[i];
lcm=lcm/gcd(lcm,aa[i])*aa[i];
}
for(int i=1; i<=n; i++)
cin>>rr[i];
for(int i=2; i<=n; i++)
{
a=aa[1],b=aa[i],c=rr[i]-rr[1];
d=ex_gcd(a,b,x,y);
if(c%d!=0)
{
flag=false;
break;
}
a=a/d,b=b/d,c=c/d;
x=(x*c%b+b)%b;
rr[1]+=aa[1]*x;
aa[1]*=aa[i]/d;
}
cout<<"Case "<<k<<": ";
if(flag==false)cout<<"-1"<<endl;
else if(rr[1]!=0)cout<<rr[1]<<endl;
else cout<<lcm<<endl;
}
return 520;
}
* 如果m[1],m[2],……m[r]是两两互素的正整数，则同余方程组
* x=a[1](mod m[1])
* x=a[2](mod m[2])
* .
* .
* .
* x=a[r](mod m[r])
* 有模M=m[1]*m[2]*……m[r]的唯一解，这就是中国剩余定理
*
* 中国剩余定理的解题思想：令MM[i]=M/m[i],因为m[1],m[2]……m[r]两两互素，因此gcd(MM[i],m[i])=1;
*即MM[i]*P[i]=1(mod m[i]),那么：a[1]*MM[1]*P[1]+a[2]*MM[2]*P[2]+……a[r]*MM[r]*P[r]就是同余方程组的解
poj1006
题目连接：http://poj.org/problem?id=1006
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int m[4],a[4];
int mm;
void ex_gcd(int a,int b,int &d,int &x,int &y)
{
if(!b)
{
x=1;
y=0;
d=a;
return ;
}
ex_gcd(b,a%b,d,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
int china(int r)
{
mm=1;
int ans=0;
int mi,d;
int x,y;
for(int i=1; i<=r; i++)
mm*=m[i];
for(int i=1; i<=r; i++)
{
mi=mm/m[i];
ex_gcd(mi,m[i],d,x,y);
ans=(ans+mi*a[i]*x)%mm;
}
if(ans<0)ans+=mm;
return ans;
}
int main()
{
int k = 0;
int p,e,i,d;
while(scanf("%d %d %d %d", &p, &e, &i, &d) != EOF)
{
k++;
if(p==-1&&e==-1&&i==-1&&d==-1)
break;
a[1] = p, a[2] = e, a[3] = i;
m[1] = 23, m[2] = 28, m[3] = 33;
int ans = china(3);
while(ans <=d)
ans += mm;
printf("Case %d: the next triple peak occurs in %d days.n", k, ans-d);
}
return 520;
}最后
以上就是沉默网络为你收集整理的同余方程组问题的全部内容，希望文章能够帮你解决同余方程组问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复