[知乎问题]六元一次方程整数解？

[vicyang]

先发链接：
https://www.zhihu.com/question/50470846/answer/121111464

六元一次方程整数解？
1999a+1299b+1499c+2799d+2499e+3299f=2328450.其中abcdef均为整数（可以为0）。
其中，a小于或等于607，b小于或等于534，c小于或等于60，小于或等于660，e小于或等于100，f小于或等于209。
这个可以通过编程或者其他什么办法求整数解吗

范围：正整数和0，以及问题中限定的范围

[vicyang]

到知乎上回答了…… 感觉在班门弄斧

递归低效率版，Perl

Code: [全选] [展开/折叠] [Download] (Untitled.pl)

1. my  @init = (0, 0, 0, 0, 0, 0);                  #初始值
2. our @e = (1999, 1299, 1499, 2799, 2499, 3299);  #系数
3. our @limit = (607, 534, 60, 660, 100, 209);     #范围
4. our $check = 2328450;                           #校验
5.  
6. func( \@init, 0 );
7.  
8. sub func
9. {
10.     our @e;
11.     our @limit;
12.     our $check;
13.  
14.     my ($ref, $lv) = (shift, shift);
15.  
16.     if ($lv <= $#$ref)
17.     {
18.         for my $n ( 0 .. $limit[$lv] )
19.         {
20.             $ref->[$lv] = $n;
21.             func( $ref, $lv+1 );
22.         }
23.     }
24.     else
25.     {
26.         my $sum = 0;
27.         for my $idx ( 0 .. $#$ref )
28.         {
29.             $sum += $ref->[$idx] * $e[$idx];
30.         }
31.         if ($sum == $check)
32.         {
33.             print join(", ", @$ref), "\n";
34.         }
35.     }
36. }

暴力6层循环，C语言版

Code: [全选] [展开/折叠] [Download] (Untitled.c)

1. #include <stdio.h>
2.  
3. int main(int argc, char *argv[])
4. {
5.     long a,b,c,d,e,f;
6.     long limit[6] = {607, 534, 60, 660, 100, 209};
7.     long coe[] = {1999, 1299, 1499, 2799, 2499, 3299};
8.     long sum;
9.  
10.     for (a = 0; a <= limit[0]; a++ ) {
11.     for (b = 0; b <= limit[1]; b++ ) {
12.     for (c = 0; c <= limit[2]; c++ ) {
13.     for (d = 0; d <= limit[3]; d++ ) {
14.     for (e = 0; e <= limit[4]; e++ ) {
15.     for (f = 0; f <= limit[5]; f++ ) {
16.  
17.         sum = a*coe[0] + b*coe[1] + c*coe[2] +
18.               d*coe[3] + e*coe[4] + f*coe[5];
19.  
20.         if (sum == 2328450)
21.         {
22.             printf("%d %d %d %d %d %d\n", a,b,c,d,e,f);
23.         }
24.  
25.     }}}}}}
26.     return 0;
27. }

6层循环，批处理版

代码: 全选

@echo off &setlocal enabledelayedexpansion

set var=a b c d e f
set /a a=607, b=534, c=60, d=660, e=100, f=209
set /a exp=0, check=2328450

for %%x in ( %var% ) do (
    set fo="for /l %%%%x in (0, 1, !%%x!) do (!fo!"
    set end="!end!)"
    set exp= !exp! + %%%%x
    set echo=!echo! %%%%x
)

%fo:"=%
    set /a sum = %exp%
    if "!sum!" == "%check%" (
        echo %echo%
        )
 
%end:"=%
pause

分而治之，Perl版

Code: [全选] [展开/折叠] [Download] (Untitled.pl)

1. our $check = 2328450;                           #校验
2. our @limit = (607, 534, 60, 660, 100, 209);     #范围
3. our @e = (1999, 1299, 1499, 2799, 2499, 3299);  #系数
4.  
5. my $sum;
6. my %hash;
7.  
8. print "step1\n";
9. for my $a ( 0 .. $limit[0] )
10. {
11.     for my $b ( 0 .. $limit[1] )
12.     {
13.         for my $c ( 0 .. $limit[2] )
14.         {
15.             $sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
16.             $hash{$sum} = [$a, $b, $c];
17.         }
18.     }
19. }
20.  
21. print "step2\n";
22. my $part1;
23. my $part2;
24. open $WRT, ">:raw", "D:/Result.txt";
25. for my $d ( 0 .. $limit[3] )
26. {
27.     for my $e ( 0 .. $limit[4] )
28.     {
29.         for my $f ( 0 .. $limit[5] )
30.         {
31.             $part2 = $d * $e[3] + $e * $e[4] + $f * $e[5];
32.             $part1 = $check - $part2;
33.             if ( exists $hash{$part1} )
34.             {
35.                 print $WRT join( ", ", @{ $hash{$part1} }, $d, $e, $f );
36.                 print $WRT "\n";
37.             }
38.         }
39.     }
40. }
41. close $WRT;
42. <STDIN>;

i7，用时约40秒，输出282,819 KB大小的文件。
这里有一个疏忽，

$sum = $a * $e[0] + $b * $e[1] + $c * $e[2];
$hash{$sum} = [$a, $b, $c];


$sum 可能是相同的值，从而忽略了一些不同情况下的 a b c ，保存所有情况下的a b c，提示 out of memory。虽然可以保存到文件，然后建立索引。。。

[happy886rr]

解六元线性丢番图方程1999a+1299b+1499c+2799d+2499e+3299f=2328450 (约数条件a,b,…,f∈N)时，可先顺次求出最大公约数(1999,1299)=d2, (d2,1499)=d3, (d3,2799)=d4, (d4,2499)=d5, (d5,3299)=d6;易知d2=d3=d4=d5=d6=1;
以下为伪码，只示思路。

Code: [全选] [展开/折叠] [Download] (Untitled.c)

1. 则化为ti型参数方程:
2. {
3.     1999a+1299b=t2
4.     t2+1499c=t3
5.     t3+2799d=t4
6.     t4+2499e=t5
7.     t5+3299f=2328450    //其中t2~t5为参数
8. }
9.  
10. 由于你说a,b,…,f∈N自然数，这就好办了，很容易的。从最后一个ti型参数方程“t5+3299f=2328450”入手也就是t5=2328450-3299f，这是标准的二元线性丢番图，先找出其一个解{f=0,t5=2328450},
11. 直接套公式(易求出)其通解为：
12. {
13.     f=0+θ,               //由于题目还给出f<=209,所以θ∈[0,209]闭区
14.     t5=2328450-3299θ;    //其中θ∈[0,209]
15. }
16.  
17. 这样f的解就都求出来，直接把求得的t5参值代入到倒数第二个ti型参数方程“t4+2499e=t5”中，继续重复调用二元线性丢番图丢番图的求解公式，得到全部e的解和t4参值。
18.  
19. 依次类推
20. {
21.     倒数第三个ti型参数方程
22.     倒数第四个ti型参数方程
23.     倒数第五个ti型参数方程
24. }

由于纯粹数学原理直接套公式，结合a,b,…,f的取值范围限制，用大量if判断break中断，从而降到极少量的for循环，而且关键是一个解都不漏，还有结合1999a+1299b=t2的特殊性(只有这个才需要打表)。mathematics软件也是用的这方法，解丢番图，就调用丢番图模型去解。