dmy#139
原题编辑此页

[R23D]三角形数阵

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

思路

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

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

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

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

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

给定 xx，算法分两步：

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

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

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

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

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

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

复杂度

每组数据一次 O(log⁡x)O(\log x) 的二分，之后 O(1)O(1) 推出坐标。总复杂度 O(Tlog⁡x)O(T \log x)，对 T≤103T \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(): Int64 {
    let reader = getStdIn()
    let t = Int64.parse(reader.readln().getOrThrow())
    for (_ in 0..t) {
        solve(reader)
    }
    return 0
}