题目162：十六进制数字

欧拉计划 · 发表于 2016-9-14 23:13:24

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 2016-9-14 23:15 编辑

Hexadecimal numbers

In the hexadecimal number system numbers are represented using 16 different digits:

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

The hexadecimal number AF when written in the decimal number system equals 10x16+15=175.

In the 3-digit hexadecimal numbers 10A, 1A0, A10, and A01 the digits 0,1 and A are all present.
Like numbers written in base ten we write hexadecimal numbers without leading zeroes.

How many hexadecimal numbers containing at most sixteen hexadecimal digits exist with all of the digits 0,1, and A present at least once?
Give your answer as a hexadecimal number.

(A,B,C,D,E and F in upper case, without any leading or trailing code that marks the number as hexadecimal and without leading zeroes , e.g. 1A3F and not: 1a3f and not 0x1a3f and not $1A3F and not #1A3F and not 0000001A3F)

题目：

十六进制系统中，数字用 16 个不同的字符表示

0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F

16 进制数字 AF 用 10 进制表示就是 10x16+15=175。

在 3 位的 16 进制数字 10A ，1A0，A10 和 A01 中，0，1，A 均全部出现。

像 10 进制数一样，我们写 16 进制时，不要前导的 0。

请问，0，1，A 均出现至少一次的，最多 16 位的，16 进制数字有多少个？

请用 16 进制数字回答。

A，B，C，D 是大写字母，没有前导或末尾代码标志着它们是 16 进制数，也没有前导 0。所以，1A3F 不能写成 1a3f 0x1a3f ，$1A3F #1A3F 以及 0000001A3F）

永恒的蓝色梦想 · 发表于 2020-4-18 14:45:59

本帖最后由永恒的蓝色梦想于 2020-5-5 18:17 编辑

照搬的外国大神的代码，尽管我完全没看懂……

s = 0
for n in xrange(3, 17): 
    s += 15*16**(n-1) + 41*14**(n-1) - (43*15**(n-1) + 13**n)

print "Project Euler 162 Solution = %X" % s

我改写的Python3版本

print("%X"%sum(15*16**n+41*14**n-43*15**n-13**(n+1)for n in range(2,16)))

guosl · 发表于 2020-12-2 08:06:28

本帖最后由 guosl 于 2022-10-3 22:09 编辑

对0，1，A来说其指数型母函数是：e^x - 1，对其它值的指数型母函数是：e^x。
所以一定包含0,1,A的0到F的字符串的指数型母函数是：e^(13x)*(e^x-1)^3，
展开来为：e^(16x) - 3e^(15x) + 3e^(14x) - e^(13x)
或写成：∑(16^n-3*15^n+3*14^n-13^n)
而在上面的计算中还包括了首导为0的字符串
那么首导为零的字符串后面的字符串的指数型母函数为：e^(14x)*(e^x-1)^2
展开后为：e^(16x)-2e^(15x)+e^(14x)
或写成：∑(16^n-2*15^n+14^n)
那么含有0,1,A的长度为n的十六进制数的个数是：16^n-3*15^n+3*14^n-13^n - 16^(n-1)+2*15^(n-1)-14^(n-1)
整理后得：15*16^(n-1)-43*15^(n-1)+41*14^(n-1)-13^n
将n=3,...,16代入即值相加可得结果。
不过其最后结果的数值太大，我们用大数库mpir来编程。
最后结果是：3D58725572C62302

#include <iostream>
#include <string>
#include <mpir.h>
#include <mpirxx.h>
using namespace std;

int main(void)
{
  mpz_class z16, z15, z14, z13;
  z16 = 16 * 16;
  z15 = 15 * 15;
  z14 = 14 * 14;
  z13 = 13 * 13 * 13;
  mpz_class z, sum = 0;
  for (int i = 3; i <= 16; ++i)
  {
    z = 15 * z16 - 43 * z15 + 41 * z14 - z13;
    sum += z;
    z13 *= 13;
    z14 *= 14;
    z15 *= 15;
    z16 *= 16;
  }
  string s = sum.get_str(16);
  char s1[32];
  memset(s1, 0, sizeof(s1));
  for (int i = 0; i < s.length(); ++i)
    s1[i] = towupper(s[i]);
  cout << s1 << endl;
  return 0;
}

账号		自动登录	找回密码
密码			立即注册