这里无意中引出了一个恒等式:lcm(a, b) * gcd(a, b) = ab.这个等式可以通过算术基本定理进行证明,证明过程可以通过图一-4-1秒懂.
[例题6]一个n位十进制数(n <= 1000000)必定包含1,2,3,4四个数字,现在将它顺序重排,求给出一种方案,使得重排后的数是7的倍数.
取出1,2,3,4后,将剩下的数字随便排列得到一个数a,令剩下的四个数字排列出来的数为b,那么就是要找到一种方案使得(a*10000 + b) % 7等于0.
并且在53*53*53次计算之内必定能够找到循环节,这个是显而易见的.
这个函数揭示了一个约定俗成的概念,即任何非零整数和零的最大公约数为它本身.
但是可以发现