[R23D]三角形数阵

对于 $100\%$ 的数据，$1 \leq T \leq 10^3$，$1 \leq x \leq 10^{18}$。

思路

把三角形数阵的格子记为 $(r, c)$，其中第 $r$ 行有 $r$ 个格子，即 $1 \leq c \leq r$。填充路径沿着一条条「逆对角线」（$r + c$ 为常数）进行，每填满一条就移到下一条。

先确定 每条逆对角线的长度。考虑满足 $r + c = d$ 且 $c \leq r$ 的格子数：

• $c$ 的取值范围是 $1 \leq c \leq \lfloor d / 2 \rfloor$，所以对角线 $d$ 的长度为 $\lfloor d/2 \rfloor$。
• 于是对角线 $d = 2, 3$ 长度均为 $1$；$d = 4, 5$ 长度均为 $2$；$d = 6, 7$ 长度均为 $3$……

也就是说，每个长度 $s$ 恰好出现两次（对应 $d = 2s$ 与 $d = 2s + 1$）。所有长度 $< s$ 的对角线贡献的格子总数为 $2 \cdot (1 + 2 + \cdots + (s-1)) = s(s-1)$；而长度恰为 $s$ 的两条对角线总共再贡献 $2s$ 个格子，覆盖编号区间

$[\,s(s-1)+1,\ s(s+1)\,].$

给定 $x$，算法分两步：

1. 求 $s$：找到最小的 $s$ 使得 $s(s+1) \geq x$。由于 $x \leq 10^{18}$，$s$ 最大约 $10^9$，直接用浮点开方有精度风险，改为 整数二分 即可，比较式 mid * (mid + 1) 在 $s \leq 10^9$ 时不会溢出 Int64。
2. 定位坐标：记当前 $s$ 的两条对角线内偏移

$\text{off} = x - s(s-1) - 1 \in [0,\ 2s-1].$

每条对角线都从 最左下角（$r$ 最大处）开始，沿右上方向（$r$ 减、$c$ 增）逐格填。设对角线内的步进 $j$（从 $0$ 开始），则格子为 $(r_0 - j,\ 1 + j)$，其中 $r_0$ 是该对角线起点的行号。

• 若 $\text{off} < s$：落在长度 $s$ 的 第一条 对角线（$d = 2s$），起点为 $(r_0, c_0) = (2s-1, 1)$。令 $j = \text{off}$，得 $r = 2s - 1 - j$，$c = 1 + j$。
• 否则：落在 第二条 对角线（$d = 2s + 1$），起点为 $(r_0, c_0) = (2s, 1)$。令 $j = \text{off} - s$，得 $r = 2s - j$，$c = 1 + j$。

验证样例 $x = 12$：求最小 $s$ 使 $s(s+1) \geq 12$，$s = 2$ 时 $2 \cdot 3 = 6 < 12$，$s = 3$ 时 $3 \cdot 4 = 12 \geq 12$，故 $s = 3$。此时覆盖区间为 $[\,3 \cdot 2 + 1,\ 3 \cdot 4\,] = [7, 12]$，$\text{off} = 12 - 3 \cdot 2 - 1 = 5$。因 $5 \geq s = 3$，走第二条分支：$j = 5 - 3 = 2$，$r = 2 \cdot 3 - 2 = 4$，$c = 1 + 2 = 3$，即 $(4, 3)$，与样例一致。同理 $x = 13$ 落入下一段（$s = 4$，第一条对角线 $d = 8$ 起点 $(7, 1)$），得 $(7, 1)$；$x = 16$ 同段、$\text{off} = 7$、$j = 3$，得 $(4, 4)$，三个样例全部吻合。

这里的 $s = 3$ 对应两条长度为 $3$ 的逆对角线 $d = 2s, 2s+1 = 6, 7$，共 $6$ 格，编号 $7 \sim 12$；编号 $13$ 起进入长度为 $4$ 的对角线 $d = 8$。

复杂度

每组数据一次 $O(\log x)$ 的二分，之后 $O(1)$ 推出坐标。总复杂度 $O(T \log x)$，对 $T \leq 10^3$ 远在时限内。

仓颉实现

// [R23D]三角形数阵
// 自然数 1,2,3,... 填入三角形数阵 (第 i 行 i 个数, c<=r).
// 沿逆对角线 (常数 r+c) 填充, 从最左下角开始填满一条后移到下一条.
// 对角线 d=r+c 的长度 (受 c<=r 限制):
//   d=2,3 -> 长度 1,1
//   d=4,5 -> 长度 2,2
//   d=6,7 -> 长度 3,3
// 一般地, 每个长度 s 出现两次 (d=2s 和 d=2s+1).
// 长度 1..s-1 共有 s(s-1) 个数; 长度 s 的两条对角线覆盖 [s(s-1)+1, s(s+1)].
// 给定 x:
//   1) 求最小 s 使 s(s+1) >= x (整数二分, 避免浮点误差).
//   2) off = x - s(s-1) - 1  (0-indexed, 范围 [0, 2s-1]).
//   3) 若 off < s: 第 1 条长度 s 的对角线, d=2s, 从左下 (r=2s-1,c=1) 起向右上,
//        j=off, r=2s-1-j, c=1+j.
//      否则: 第 2 条长度 s 的对角线, d=2s+1, 从左下 (r=2s,c=1) 起向右上,
//        j=off-s, r=2s-j, c=1+j.

import std.convert.*
import std.env.*

func solve(reader: ConsoleReader) {
    let x = Int64.parse(reader.readln().getOrThrow())
    // 二分求最小 s 使 s*(s+1) >= x, s >= 1.
    var lo: Int64 = 1
    var hi: Int64 = 2000000000 // sqrt(2)*1e9 > 需要的, s*(s+1)>=1e18 -> s 约 1e9
    while (lo < hi) {
        var mid: Int64 = lo + ((hi - lo) >> 1)
        // mid*(mid+1) 可能溢出 Int64 (1e9*1e9=1e18 接近上限), 用 mid*(mid+1) 与 x 比较
        // mid*(mid+1) <= mid^2 + mid, mid<=1e9 时 < 1e18+1e9 不溢出
        var prod: Int64 = mid * (mid + 1)
        if (prod < x) {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    let s = lo
    let off = x - s * (s - 1) - 1
    var r: Int64
    var c: Int64
    if (off < s) {
        let j = off
        r = 2 * s - 1 - j
        c = 1 + j
    } else {
        let j = off - s
        r = 2 * s - j
        c = 1 + j
    }
    println("${r} ${c}")
}

main() {
    let reader = getStdIn()
    let t = Int64.parse(reader.readln().getOrThrow())
    for (_ in 0..t) {
        solve(reader)
    }
}