Project Euler #162: Hexadecimal numbers

点击查看原题说明

不妨设位数为n,从右往左一次为第1,2,3...n位,第n位不能是0,待求的集合是同时包含0,1,A并且最高位不为0的数的个数,这是一道典型的集合问题。

令 c = {第n位不为0的所有n位数},

x = {不包含0的所有n位数(第n位不能为0)},

y = {不包含1的所有n位数(第n位不能为0)},

z = {不包含A的所有n位数}

记符号^为集合取反操作(加上划线不方便)。

要求的结果就是 x∩y∩z。

根据集合运算法则可知 x∩y∩z = c - ^(x∩y∩z)

根据德摩根定律 ^(x∩y∩z) = (^x)∪(^y)∪(^z)

= ^x + ^y + ^z - ^x*^y - ^x*^z -^y*^z + ^x*^y*^z

由于第n位不能为0, 所以c = 15 * 16n-1

^x = 15 * 15n-1

对于^y和^z,除了有不包含1或A的限制,还有一个隐含限制条件,就是最高位不能为0,因此 ^y = ^z = 14*15n-1

同理,对于 ^x * ^y = ^x * ^z = 14 * 15n-1,^y * ^z = 13*15n-1

而 ^x * ^y * ^z = 13n

因此,x∩y∩z = 15*16n-1 - (15*15n-1 +14*15n-1*2 - 14*15n-1 - 13*15n-1 + 13n) ,化简得到:15 x 16(n-1) + 41 x 14(n-1) – (43 x 15(n-1) + 13n)

最后的化简公式得到之后,这道题目就迎刃而解了。

Show Comments

Get the latest posts delivered right to your inbox.