• 任意一个三位数乘以1001，乘积的末尾三位一定等于它本身
    • 234*1001=234234
    • 120*1001=120120
    • 123*1001=123123
  1. 123这个数，乘以91得到了11193，接着我去掉两位只保留后三位，把193
  • 123*91%1000 == 193
  1. 知道我的结果193后，再用193乘以11，得到了2123。而2123的末尾三位数，就是我的想的123

  • 193*11%1000 == 123

  • 123*91%1000*11%1000 == 123*91*11%1000

  • 如果最后要对乘积取余，那么在事先对乘数取余不会对结果造成影响

  • 得到91和193后，要做的其实是解一个方程：

    • 91 * x mod 1000 = 193

  • 有这样一个原理：

    • ab互质，且a * x mod b = c，那么a * n * x mod b = n * c。 这时他迅速地算出
    • 91 * 11 mod 1000 = 1，那么91 * 11 * 193 mod 1000 = 193。
    • 就是说11 * 193 mod 1000 = 123，一定等于我想的三位数

xa%b=c ==> xan%b=nc

x91%1000=193 ==> x91n%1000=n193 ==> n==1 ==> x*91%1000=193