今天要討論的問題是解方程，其中是奇質數。

?

引理：

?

證明：由費馬小定理，

?

引理：方程有解當且僅當

?

定理：設滿足不是模的二次剩余，即無解，那么是二次

?????剩余方程的解。

?

證明：由，前面的等號用二項式定理和，后面的等

???? 號用了費馬小定理和是模的二次非剩余。然后

?

???? ?

?

在算法實現的時候，對的選擇可以隨機，因為大約有一半數是模的二次非剩余，然后快速冪即可。

?

?

題目：http://acm.timus.ru/problem.aspx?space=1&num=1132

?

題意：求二次同余方程的解。

?

代碼：

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h>using namespace std; typedef long long LL;LL quick_mod(LL a, LL b, LL m) {LL ans = 1;a %= m;while(b){if(b & 1){ans = ans * a % m;b--;}b >>= 1;a = a * a % m;}return ans; }struct T {LL p, d; };LL w;//二次域乘法 T multi_er(T a, T b, LL m) {T ans;ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m;ans.d = (a.p * b.d % m + a.d * b.p % m) % m;return ans; }//二次域上快速冪 T power(T a, LL b, LL m) {T ans;ans.p = 1;ans.d = 0;while(b){if(b & 1){ans = multi_er(ans, a, m);b--;}b >>= 1;a = multi_er(a, a, m);}return ans; }//求勒讓德符號 LL Legendre(LL a, LL p) {return quick_mod(a, (p-1)>>1, p); }LL mod(LL a, LL m) {a %= m;if(a < 0) a += m;return a; }LL Solve(LL n,LL p) {if(p == 2) return 1;if (Legendre(n, p) + 1 == p)return -1;LL a = -1, t;while(true){a = rand() % p;t = a * a - n;w = mod(t, p);if(Legendre(w, p) + 1 == p) break;}T tmp;tmp.p = a;tmp.d = 1;T ans = power(tmp, (p + 1)>>1, p);return ans.p; }int main() {int t;scanf("%d", &t);while(t--){int n, p;scanf("%d %d",&n,&p);n %= p;int a = Solve(n, p);if(a == -1){puts("No root");continue;}int b = p - a;if(a > b) swap(a, b);if(a == b)printf("%d\n",a);elseprintf("%d %d\n",a,b);}return 0; }

?

接下來我們來解另一個二次同余方程的解，其中，并且是奇質數。方法如下

?

先求出方程的一個解，那么進一步有

?

?????

?

我們知道

?

??????

?

那么也就是說

?

??????

?

可以證明和，那么最終得到

?

???????

?

這里由于不是素數，所以求逆元用擴展歐幾里得算法即可。

?

?

例如：求方程的解

?

分析：利用上述方法求得，最終解得。

?

?

?

?

總結

以上是生活随笔為你收集整理的二次同余方程的解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。