853. i-1 进制

单点时限: 2.0 sec

内存限制: 512 MB

在采用进位计数的数字系统中,如果使用的数码依次为 $0,1,2,\ldots,R-1$,总共 $R$ 个数码,则称其为基 $R$ 数制或 $R$ 进制。$R$ 称为该数制的“基数”($Radix$),例如,十进制的基数是 $10$(数码为: $0,1,2,\ldots,9$),二进制的基数是 $2$(数码为: $0,1$),八进制的基数是 $8$(数码为: $0,1,2,\ldots,7$)。

现有一种特殊的按位计数系统,该系统采用的基数为复数 $-1+i $(其中 $i$ 表示 $ \sqrt{-1} $ )。在$ -1+i $ 进制系统中,所有“复数整数”(实部和虚部都为整数的复数,这种复数在数学上称为高斯整数)都可以表示成一个“数”,该“数”只含有 $0,1$ 两个数码,不需要正负符号或其他常规手段,而且每个“复数整数”只有唯一一种表示方法。例如:整数 $2$ 用 $ -1+i $ 进制表示出来是1100

任意一个“复数整数” $a+bi$ ($a,b$ 均为整数) 可采用如下算法转换为$-1+i$ 进制表示:

1、$a+bi$ 除以 $-1+i $ 得到商 $q$ 和余数 $r$ ,商$q$ 也为“复数整数”,余数 $r$ 为 $0$ 或 $1$。

​ 令 $q=q_r+q_ii$ ($q_r$ 与 $q_i$ 均为整数,分别表示商 $q$ 的实部与虚部),

​ $q,r$ 必满足下式: $ a+bi= (q_r+q_ii)(-1+i) + r$

​ 如果 $a,b$ 均为偶数或均为奇数,则令 $r$ 为 $0$。

​ 此外,如果 $a,b$ 一奇一偶,则令 $r$ 为 $1$。

2、重复第一步用商 $q$ 除以 $-1+i $ 记录下余数 $r$,直到商为 $0$,运算过程结束。

3、从下往上读取余数,就可得到 “复数整数” $a+bi$ 的 $-1+i$ 进制表示。

例如:整数 $2 = 2+ 0i $ 的运算过程:

整数 $2$ 的实部和虚部都是偶数,所以余数为 $0$ ,$\frac{2}{-1+i} =(-1-i)$ 余 $0$

$-1-i$ 的实部和虚部均为奇数,所以余数为 $0$,$\frac{-1-i}{-1+i}=i$ 余 $0$

$i$ 的实部为偶数,虚部为奇数,所以余数为 $1$,$\frac{i}{-1+i}=1$ 余 $1$

$1$ 的实部为奇数,虚部为偶数,所以余数为 $1$,$\frac{1}{-1+i}=0$ 余 $1$

商为 $0$,运算结束,从下往上读取,得到整数 $2$ 用$-1+i$进制表示为1100

下表列出了 $-1+i$ 进制的位串00001111对应的十进制下的“复数整数”。

$-1+i$ 进制 十进制下的复数整数
0 $0$
1 $1$
10 $ -1+i $
11 $i$
100 $-2i$
101 $ 1-2i $
110 $ -1-i $
111 $ -i $
1000 $2+2i$
1001 $3+2i$
1010 $1+3i$
1011 $2+3i$
1100 $2$
1101 $3$
1110 $ 1+i $
1111 $ 2+i $

输入一个 $ -1+i$ 进制下的数(为了简化,我们将0,1位串用一个十六进制整数表示),输出其对应的十进制下的“复数整数” $a+bi$。

输入格式

在一行中输入一个 $ -1+i$ 进制下的数(十六进制表示,使用 0~9 以及大写 A~F)。

  • 30% 的数据保证答案的 $|a|, |b| \leq 100$;
  • 50% 的数据保证答案的 $|a|, |b| \leq 2~147~483~647$;
  • 85% 的数据保证答案的 $|a|, |b| \leq 9~223~372~036~854~775~807$;
  • 100% 的数据保证答案的 $|a|, |b| \leq 10^{1000}$;

输出格式

在一行中输出对应的十进制下的“复数整数” $a+bi$($a,b$均为整数),省略的情况与正常书写复数时一致,请参考上面的表格以及样例。

样例

Input
0x21
Output
5-4i
Input
0x2
Output
-1+i
Input
0x1C
Output
-2
Input
0x9
Output
3+2i

61 人解决,248 人已尝试。

81 份提交通过,共有 1417 份提交。

6.4 EMB 奖励。

创建: 6 年,6 月前.

修改: 1 年,9 月前.

最后提交: 8 月,3 周前.

来源: N/A