2 shunfurh shunfurh 于 2017.08.30 00:48 提问

Diophantine Equations

Alice: Hi Bob! Let's play a game.

Bob: Oh no! It's boring because both of us always choose the optimal strategy.

Alice: Well, then let's solve some Diophantine equations. What's the integer solutions of x2 + y2 = n if n is a fixed positive integer?

Bob: Er.. It's easy to get the solutions when n is a prime or 1. But it's a bit hard to solve this equation when n is a composite number.

Alice: Do you know Brahmagupta-Fibonacci identity? It says that the product of two sums each of two squares is itself a sum of two squares. Specifically: (a2 + b2)(c2 + d2) = (ac + bd)2 + (ad - bc)2 = (ac - bd)2 + (ad + bc)2. When n is a composite number, perhaps the solutions when n is a prime can be combined via this indentity.

Bob: Yes, the Brahmagupta-Fibonacci identity helps a lot. Now we can solve the equation easily. Let's solve some other equations. What about the integer solutions of x2 + y2 + z2 = A and x + y + z = B?

Alice: It's similar to the former equation but more complicated. Let's write a program to solve it.

Bob: Ok! It seems that we should get the decomposition of 3A - B2 first. And when 3A - B2 is less than zero, there cannot be any integer solutions.

Alice: I can write the prime factorization part. Can you complete the remaining part?

Bob doesn't know how to write a program. He turned to you for help. You are given two integers A and B. The prime factors of 3A - B2 will also be given. You should output all the integer solutions of x2 + y2 + z2 = A and x + y + z = B. Because of the symmetry, only the integer solutions (x, y, z) that x <= y <= z are required.

Input

There are multiple test cases. The first line of input contains an integer T (about 2000) indicating the number of test cases. For each test case:

There are two or more integers in one line. The first two integers are A (0 <= A <= 1018) and B (-109 <= B <= 109) respectively. The following integers in the same line are the prime factors of 3A - B2. If 3A - B2 is less than 2, no prime factors will be given.

Output

For each test case, output a label "Case #id:" first where id (starting from 1) is the case number. The following lines should be all the integer solutions (listed in x increasing order). For each integer solution, there should be three integer numbers x, y and z separated by a space.

You can assume that the total output will be no more than 20000 lines.

Sample Input

7
10 2 2 13
3 -3
1 1 2
15 -7
467716406 4 2 7 13 19
999278059394184698 1000000000 2 999007 999907 1000003
666666666666666645 -1 2 999999999999999967
Sample Output

Case #1:
-1 0 3
Case #2:
-1 -1 -1
Case #3:
0 0 1
Case #4:
Case #5:
-17655 8609 9050
-17641 8175 9470
-17554 7131 10427
-17494 6677 10821
-17410 6159 11255
-17215 5210 12009
-17059 4586 12477
-16773 3611 13166
-16591 3065 13530
-15954 1427 14531
-15499 426 15077
-15225 -130 15359
-14641 -1225 15870
-14323 -1779 16106
-14029 -2269 16302
-13714 -2773 16491
-13398 -3259 16661
-12966 -3895 16865
-12615 -4390 17009
-12265 -4866 17135
-11859 -5398 17261
-10585 -6945 17534
-9766 -7855 17625
-9298 -8349 17651
Case #6:
-325445947 576237380 749208567
-325096053 574086620 751009433
-324917875 573008543 751909332
-324556125 570853457 753702668
Case #7:
-641498974 163610588 477888385

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.14 23:49
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Hilbert 第十问题(Diophantine Equations)
Hilbert 第十问题(Diophantine Equations)
基于Matlab求解diophantine方程
function [d,f,e]=sindiophantine(a,b,c,k) %********************************************************* %功能:单步Diophanine方程的求解 %调用格式:[d,f,e]=sindiophantine(a,b,c,t) %输入参数:多项式A、B、C系数(行向量)及纯滞后(共4个) %
Differential Equations and Linear Algebra(4th) 无水印原版pdf
Differential Equations and Linear Algebra(4th) 英文无水印原版pdf 第4版 pdf所有页面使用FoxitReader、PDF-XChangeViewer、SumatraPDF和Firefox测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
杭电 HDU ACM 1496 Equations
Equations Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6065    Accepted Submission(s): 2455 Problem Description Consider equations h
The Diophantine Equation hdu 3270
每天一题萌萌哒 The Diophantine Equation Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1130    Accepted Submission(s): 290 Problem Descrip
Partial Differential Equations
Partial Differential Equations - An Introduction - W. Strauss (Wiley, 1992) WW.djvu
完整清晰的《Partial Differential Equations》第二版电子版+勘误表 (Lawrence C. Evans)
Lawrence C. Evanns 的《偏微分方程》第二版电子版+勘误表,非扫描版,不缺页,本人亲自完善的,页面文字除本人补充进去的17个缺页内容外可复制,网络上搜不到。
Partial Differential Equations with Fourier Series and Boundary Value Problem
关于偏微分方程的书,第二版 Nakhle H. Asmar著 813页
丢番图方程
丢番图,公元三世纪,古希腊数学家。 整系数代数多项式方程统称为丢番图方程(Diophantine Equation)。1. 整数解对于丢番图方程,数学家们最感兴趣的一个传统问题还是其是否有整数解(或自然数解)。2x−2y=1 2x-2y=1 则没有整数解,左边为偶数,右边是奇数。
POJ 1100 Dreisam Equations 笔记
在等式两边添加加、减、乘三种符号使两边相等。除括号外,三个符号的优先级相等。