[問題案] (Addition/Multiplication/Division of Hex Big Integers)

[kzrnm]

Problem name	Problem ID
Addition of Hex Big Integers	addition_of_hex_big_integers
Multiplication of Hex Big Integers	multiplication_of_hex_big_integers
Division of Hex Big Integers	division_of_hex_big_integers

#941 系列の問題は $10^{2 \times 10^6}$ の制約がありますが、基数を $2^{32}$ や $2^{64}$ などのバイナリで管理する場合は文字列⇄バイナリの変換が $(NlogN)^2$ 程度かかるのでそこがボトルネックになってしまいます。

2進数や16進数ならば高速にパースできるので入出力が16進数であるパターンもほしいです。

Problem

Addition of Hex Big Integers

@{lang.en} This problem has $T$ cases.
Given hexadecimal integers $A$ and $B$, print $A+B$.

@{lang.ja} この問題は $T$ ケースあります。
16進整数 $A, B$ が与えられます。$A+B$ を出力してください。

@{lang.end}

Multiplication of Hex Big Integers

@{lang.en} This problem has $T$ cases.
Given hexadecimal integers $A$ and $B$, print $AB$.

@{lang.ja} この問題は $T$ ケースあります。
16進整数 $A, B$ が与えられます。$AB$ を出力してください。

@{lang.end}

Division of Hex Big Integers

@{lang.en} This problem has $T$ cases.
Given a hexadecimal non-negative integer $A$ and a hexadecimal positive integer $B$, print hexadecimal integers $q, r$ satisfying the following equation:

@{lang.ja} この問題は $T$ ケースあります。
16進非負整数 $A$ と16進正整数 $B$ が与えられます。次の式を満たす整数 $q, r$ を出力してください。

@{lang.end}

• $q = \left \lfloor \frac{A}{B} \right \rfloor$
• $A = qB + r$

Constraint

Addition

• $0 \leq |A|, |B| < 16^{1.6 \times 10^6}$

Multiplication

• $0 \leq A, B \lt 16^{1.6 \times 10^6}$

Division

• $0 \leq A \lt 10^{1.6 \times 10^6}$
• $1 \leq B \lt 10^{1.6 \times 10^6}$

Input

$T$
$A$ $B$
 $\vdots$
$A$ $B$

Output

Addition

$A+B$
 $\vdots$
$A+B$

Multiplication

$AB$
 $\vdots$
$AB$

Division

$q$ $r$
 $\vdots$
$q$ $r$

Note / Disucussion

• プリフィックスとして 0x とつけるか
  • いらなそう
• 16進表現の説明が必要では
  • FFFFFFFF ← $-1$ の2の補数とも解釈できる
  • サンプルに FFFFFFFF は $4294967295$, -FFFFFFFF は $-4294967295$ みたいなのがわかるのがあれば十分か

[maspypy]

ありがとうございます、大丈夫そうです。