當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

表为平方和终极版

發(fā)布時(shí)間：2024/4/11 编程问答 37 豆豆

生活随笔收集整理的這篇文章主要介紹了表为平方和终极版小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

聲明：本片文章在我的草稿箱已經(jīng)塵封很久了，初稿時(shí)間是2014年9月8日，如下

?????

???? 為什么我一直沒(méi)有發(fā)出來(lái)呢？是因?yàn)槲业拇a沒(méi)有得到Yes，由于參加工作了，以后來(lái)研究的時(shí)間相對(duì)

???? 少點(diǎn)，現(xiàn)在發(fā)表出來(lái)希望有高手能指出錯(cuò)誤之處，共同進(jìn)步，謝謝！

以前寫過(guò)表為平方和初級(jí)版，鏈接為http://blog.csdn.net/acdreamers/article/details/10083393，

主要的問(wèn)題是求形如丟番圖方程的解。今天我將來(lái)探討另一類丟番圖方程的解，即的

解。當(dāng)然，我們需要先對(duì)素因子分解，得到形如的方程，其中為奇素?cái)?shù)。根據(jù)的不同，方程有

解的條件也不一樣。比如

（1）時(shí)，有解的條件是

（2）時(shí)，有解的條件是

接下來(lái)，我會(huì)重點(diǎn)以一道經(jīng)典題目的解析來(lái)說(shuō)明此類丟番圖方程在競(jìng)賽中的應(yīng)用。

題目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3815

題意：給定兩個(gè)正整數(shù)和，其中和，輸出所有滿足條件的三元組，并且

???? 輸出數(shù)據(jù)滿足條件。

分析：本題是2014年亞洲區(qū)域賽網(wǎng)絡(luò)預(yù)選賽（牡丹江賽區(qū)）的G題。然而現(xiàn)場(chǎng)AC率為0，接下來(lái)進(jìn)行詳細(xì)探討

???? 首先根據(jù)已知條件，我們可以得到如下

????

?????再令，則有

?????

???? 繼續(xù)消去，得到

??????

?????令，得到，再將素因子分解，分別求出解，

???? 然后合并即可，合并的時(shí)候跟丟番圖方程的合并類似，如下

???? ?

???? 現(xiàn)在的關(guān)鍵問(wèn)題是如何求解丟番圖方程，其中為奇素?cái)?shù)，此處。

?????那么有解的條件是，并且解唯一，求解和的方法跟上次類似，具體步驟如下

???? （1）先求出同余方程的最小正整數(shù)解

???? （2）對(duì)和進(jìn)行輾轉(zhuǎn)相除運(yùn)算，記錄每次的余數(shù)為（注意第一次的余數(shù)為），當(dāng)滿足條件

???????? 時(shí)停止，此時(shí)的就是，而可以通過(guò)得到，即

?????????

代碼：

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <iostream> #include <vector> #include <math.h> #include <set> #include <map>using namespace std; const int N = 255; const int M = 200005; typedef long long LL;char str[N]; LL a[N];struct Pair {LL x, y;bool operator < (const Pair &a) const{if(a.x == x) return a.y > y;return a.x > x;} }; Pair node[M];struct Res {LL x, y, z;bool operator < (const Res &a) const{if(a.x == x && a.y == y) return a.z > z;if(a.x == x) return a.y > y;return a.x > x;} };set<Pair> Set; set<Res> _Set; set<Pair> Mem; vector<LL> vec;int sign[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; int _sign[2][2] = {{-1, 1}, {1, -1}};LL multi(LL a, LL b, LL m) {LL ans = 0;a %= m;while(b){if(b & 1){ans = (ans + a) % m;b--;}b >>= 1;a = (a + a) % m;}return ans; }LL quick_mod(LL a, LL b, LL m) {LL ans = 1;a %= m;while(b){if(b & 1){ans = multi(ans, a, m);b--;}b >>= 1;a = multi(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 = (multi(a.p, b.p, m) + multi(multi(a.d, b.d, m), w, m)) % m;ans.d = (multi(a.p, b.d, m) + multi(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 Work(LL n, LL p) {if(p % 3 != 1) return -1;LL a = -1, t;while(1){a = rand() % p;t = a * a - n;w = (t % p + p) % 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; }LL Solve(LL n, LL p, LL &_x, LL &_y) {LL x = Work(n, p);if(x == -1)return -1;if(x >= p - x)x = p - x;LL t = p;LL r = x;LL limit = (LL)sqrt(1.0 * p);while(r > limit){x = r;r = t % x;t = x;}_x = r;_y = (LL)sqrt((p - r * r) / 3);return 0; }void Prepare(char str[], LL a[], int &cnt) {cnt = 0;LL ans = 0;bool flag = 0;int len = strlen(str);for(int i=0; i<=len; i++){if(str[i] >= '0' && str[i] <= '9')ans = ans * 10 + str[i] - '0';else if(str[i] == '-')flag = 1;else{if(flag) ans = -ans;a[cnt++] = ans;ans = 0;flag = 0;}} }bool getData(Pair node[], LL a[], int &cnt) {int k = 0;int _cnt = 0;for(int i = 0; i < cnt; i++){if(a[i] == 2) k++;if(k == 2){node[_cnt].x = 1;node[_cnt].y = 1;_cnt++;k = 0;}if(a[i] > 2){LL x, y;int ans = Solve(-3, a[i], x, y);if(ans == -1) return false;node[_cnt].x = x;node[_cnt].y = y;_cnt++;}}cnt = _cnt;if(k == 1) return false;return true; }void dfs(int dept, int cnt, Pair ans) {if(dept == cnt - 1){Set.insert(ans);return;}for(int i = 0; i < 4; i++){for(int j = 0; j < 2; j++){Pair _ans;_ans.x = ans.x * sign[i][0] * node[dept + 1].x + _sign[j][0] * 3 * ans.y * sign[i][1] * node[dept + 1].y;_ans.y = ans.x * sign[i][1] * node[dept + 1].y + _sign[j][1] * ans.y * sign[i][0] * node[dept + 1].x;if(Mem.find(_ans) != Mem.end()) return;Mem.insert(_ans);dfs(dept + 1, cnt, _ans);}} }void Merge(Pair node[], int cnt) {Pair ans;for(int i = 0; i < 4; i++){ans.x = sign[i][0] * node[0].x;ans.y = sign[i][1] * node[0].y;Mem.insert(ans);dfs(0, cnt, ans);} }void Filter(LL B) {set<Pair>::iterator it;for(it = Set.begin(); it != Set.end(); it++){LL a = it->x - it->y;if(a & 1) continue;a >>= 1;LL b = it->y;LL c = -a - b;LL _x = B + a - c;if(_x % 3) continue;_x /= 3;LL _y = _x - a;LL _z = _x + c;if(_x > _z) swap(_x, _z);if(_y > _z) swap(_y, _z);if(_x > _y) swap(_x, _y);Res res;res.x = _x;res.y = _y;res.z = _z;_Set.insert(res);}set<Res>::iterator _it;for(_it = _Set.begin(); _it != _Set.end(); _it++)printf("%lld %lld %lld\n", _it->x, _it->y, _it->z); }void Response(LL a[], int cnt) {LL A = a[0];LL B = a[1];LL n = 3 * A - B * B;if(n == 0 && B % 3 == 0){printf("%lld %lld %lld\n", B / 3, B / 3, B / 3);return;}if(n < 2) return;a += 2;cnt -= 2;sort(a, a + cnt);for(int i = 0; i < cnt; i++){while(n % a[i] == 0){vec.push_back(a[i]);n /= a[i];}}cnt = 0;vector<LL>::iterator it;for(it = vec.begin(); it != vec.end(); it++)a[cnt++] = *it;for(int i = cnt; i >= 1; i--)a[i] = a[i-1];a[0] = 2;cnt++;if(!getData(node, a, cnt)) return;Merge(node, cnt);Filter(B); }int main() {int T;scanf("%d", &T);getchar();for(int t = 1; t <= T; t++){vec.clear();Mem.clear();Set.clear();_Set.clear();int cnt;gets(str);Prepare(str, a, cnt);printf("Case #%d:\n", t);Response(a, cnt);}return 0; }

最后附上鳥(niǎo)神的思路，雖然我不懂，但我感覺(jué)好厲害！！！

總結(jié)

以上是生活随笔為你收集整理的表为平方和终极版的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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