关于 gcd 想必大家早已熟知辗转相除法。现提出一种O(1)算法。

如图是 IMO 29 #6数论题的解法,选自常庚哲 史济怀《数学分析教程(上册)》。
o1gcd.png


据说与 gcd 有关,由下面的程序可以看到,如果 $$ \KaTex $$

#include <iostream>
int main(){
    for (int a=1;a<=1000;a++)
        for(int b=a+1;b<=1000;b++)
            if ((a*a+b*b) % (1+a*b) ==0)
                std::cout<<a<<"    "<<b<<"    "<<(a*a+b*b) / (1+a*b)<<std::endl;
    return 0;
}

输出:

2       8       4
3       27      9
4       64      16
5       125     25
6       216     36
7       343     49
8       30      4
8       512     64
9       729     81
10      1000    100
27      240     9
30      112     4
112     418     4
请按任意键继续. . .