【概念】

1.不定方程：未知數(shù)的個(gè)數(shù)多于方程個(gè)數(shù)，且未知數(shù)受到某些限制（如要求是整數(shù)）的方程。

2.同余方程

設(shè)函數(shù)?，則稱：是關(guān)于模 m 的同余方程

3.線性：方程的未知數(shù)次數(shù)是一次

4.線性同余方程

線性同余方程是最基本的同余方程，形如??的未知數(shù)是 x 的同余式，其中，a、b 是整數(shù)，且?

【與線性同余方程有關(guān)的定理】

1.定理1：對(duì)于二元一次方程??，其等價(jià)為?，該方程有整數(shù)解的充分條件是?，若方程有整數(shù)解，則共有??個(gè)解。

2.定理2：若??、?為??的一組解，則該方程的任一解可表示為：

注意，上面兩個(gè)通解公式只能選擇其中一個(gè)，另一個(gè)再根據(jù)原方程推出。

3.定理3：若?，則方程??在??上有唯一解。

【線性同余方程的解的求法】

1.使用擴(kuò)展歐幾里德算法求方程的一組解

根據(jù)定理1，對(duì)于方程??，用擴(kuò)展歐幾里德算法求出一組?、，即令?，然后兩邊同除??，再乘以 c ，即得方程??，因此可知方程的一組解?

2.實(shí)際應(yīng)用

實(shí)際中，常常被要求去求最小的正整數(shù)的解，先通過(guò)擴(kuò)展歐幾里德算法求出方程的一組?、，再設(shè)??，通過(guò)定理2來(lái)拓展方程的解，來(lái)調(diào)整x的范圍，將??拓展為??，從而使得所得到的 x 盡可能的小，通過(guò)式子??來(lái)約束結(jié)果一定是一個(gè)正數(shù)，最后所得到的 x 即是一個(gè)最小的正整數(shù)解。?

【模版】

#include<iostream> using namespace std; int Extended_GCD(int a,int b,int &x,int &y) {if(b==0){x=1;y=0;return a;}int temp;int gcd=Extended_GCD(b,a%b,y,x);y-=x*(a/b);return gcd; } int main() {//形如 ax+by=cint a,b,c,x,y;cin>>a>>b>>c;int gcd=Extended_GCD(a,b,x,y);if(c%gcd!=0)cout<<"無(wú)整數(shù)解"<<endl;elsecout<<"該方程的一組整數(shù)解為：x="<<x*c/gcd<<",y="<<y*c/gcd<<endl;return 0; }

【例題】

• 青蛙的約會(huì)（POJ-1061）(擴(kuò)展歐幾里得)：點(diǎn)擊這里
  同題：青蛙的約會(huì)（洛谷-P1516）：點(diǎn)擊這里
• The Balance（POJ-2142）(線性同余方程)：點(diǎn)擊這里
• C Looooops（POJ-2115）(線性同余方程)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的数论 —— 线性同余方程的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。