找到所有4位吸血鬼号码

Question

我正在解决一个问题，找出所有的4位吸血鬼数字。

吸血鬼数v=x*y被定义为一个具有'n'个偶数位数的数字，通过将一对'n/2'位数的数字（其中的数字以任意顺序取自原始数）x和y相乘而形成。如果v是吸血鬼的数字，那么X&Y和被称为它的“尖牙”。

吸血鬼数量的例子有：

    1.    1260=21*60
    2.    1395=15*93
    3.    1530=30*51

我曾经尝试过蛮力算法，将给定数字的不同数字组合在一起，并将它们相乘。但这种方法效率很低，而且占用大量时间。

这个问题有没有更高效的算法解决方案？

Answer 1

或者你可以使用本页描述的吸血鬼号码的一个属性（链接自维基百科）：

皮特·哈特利发现的一个重要理论结果：

      If x·y is a vampire number then x·y == x+y (mod 9) 

证明：设mod是二进制模运算符，d(x)是x的十进制数的和。众所周知，d(x)mod9=xmod9，对于所有x。假设X·Y是吸血鬼。那么它包含与x和y相同的数字,特别是d(x·y)=d(x)+d(y)。这导致:(x·y)mod 9=d(x·y)mod 9=(d(x)+d(y))mod 9=(d(x)mod 9+d(y)mod 9）mod 9=(x mod 9+y mod 9）mod 9=(x+y)mod 9

在{（0,0）,（2,2）,（3,6）,（5,8）,（6,3）,（8,5）}

因此您的代码可能如下所示：

for(int i=18; i<100; i=i+9){          // 18 is the first multiple of 9 greater than 10
   for(int j=i; j<100; j=j+9){        // Start at i because as @sh1 said it's useless to check both x*y and y*x
       checkVampire(i,j);
   }
}

for(int i=11; i<100; i=i+9){          // 11 is the first number greater than 10 which is = 2 mod 9
   for(int j=i; j<100; j=j+9){
       checkVampire(i,j);
   }
}

for(int i=12; i<100; i=i+9){
   for(int j=i+3; j<100; j=j+9){
       checkVampire(i,j);
   }
}

for(int i=14; i<100; i=i+9){
   for(int j=i+3; j<100; j=j+9){
       checkVampire(i,j);
   }
}

// We don't do the last 2 loops, again for symmetry reasons

由于它们是每个集合中的40个元素，如{（x mod 9,y mod 9)=(0,0）；10<=x<=y<=100}，所以当一个蛮力给你10 4个迭代时，你只会做4*40=160迭代。如果考虑>=1000约束，则可以执行更少的操作，例如，可以避免检查是否j<1000/i。

现在你可以很容易地按比例放大，找到4位数以上的吸血鬼=)