2019 ICPC TOPC 簡易講評
===
###### tags: `ICPC` `TOPC` `TOPC2019`
[題組資源](https://drive.google.com/open?id=1mg3UvMZUE1l3JbuG6fLmLoVS7dn4ztxv)
本次競賽賽題由交通大學退役選手陳昇暉、莊昕宸、黃右萱協助裁判長命題，並由交通大學資工系蔡孟宗教授，以及中正大學、台灣大學、清華大學、交通大學多位退役選手審查、校對、檢驗測資與撰寫解答驗題。因本次賽事並無爭取到任何經費，在此特別感謝他們的辛勞與無私奉獻。
以下為 2019 ICPC Asia Taiwan Online Programming Contest 的競賽主席兼裁判長謝旻錚對此題組的簡易講評。
## Problem A -- Animal King Election
Problem setter: Min-Zheng Shieh
本題預設目標答對率 100% ，最終答對率近 99% 。題目說由九個公民選出下一任國王，候選人只有兩位： Tiger 跟 Lion 。而且題目保證一定都會投有效票：不是給 Tiger 就是給 Lion 。要求算出得票比較多的下一任國王。
做法有很多種，可以直接統計誰票多，就印誰。附贈的範例一行解答則是將九張票做排序，然後輸出中間的那一個，這也能得到答案。
```kotlin=
fun main() = println((1..9).map{readLine()!!}.sorted()[4])
```
在檢視答錯的同學程式碼時，發現部分同學不知道字串大小寫可能被視為相異的字串，因此答錯。如果有人未來以目標答對率 100% 命題時，請特別留意字串最好都小寫。
## Problem B -- Bags
Problem setter: Min-Zheng Shieh
本題預設目標答對率 90% ，最終答對率近 94% 。題目說要收 $n$ 個化學廢料，不能把相異的廢料收在同一個袋子，必須要用不同的袋子裝。問需要多少個袋子。其實很單純的，統計相異物品有幾個即可。最簡單的方式如參考解答，直接用個簡單集合類的容器裝，並且印出其中有幾個即可。
```kotlin=
private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}
fun main() {
val n = nextInt()
val cans = HashSet<Int>(nextInts())
println(cans.size)
}
```
這題要做一行解，比較討厭的是那個 $n$ 要讀。
```kotlin=
fun main(){readLine()?.also{println(readLine()!!.split(" ").distinct().size)}}
```
```python=
print(input()[0:0]+'%d'%len(set(input().split())))
```
命題時有考量可能隊伍不會使用容器，另法是：「排序後，靠檢查有多少組相鄰兩個數字不同，再加上一就是答案」。
## Problem C -- Change Making
Problem Setter: Min-Zheng Shieh
考量這是個經典題，只要知道原來的題目怎樣 Dynamic Programming 會通過的隊伍，應該能通過。目標答對率設定為 70% ，但最終通過的只有約 60% 。演算法課程很可能會提到 Change making problem ，只要能夠計算最佳解，並依照題面敘述計算 Greedy 解，在有限的範圍內要找出第一個不同處，應該不困難。低年級的同學沒有做出這題，請不要太過沮喪。
```kotlin=
private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ").filter{it!=""}
private fun nextInts() = nextToks().map{it.toInt()}
fun main() {
var dp = ArrayList<Int>(listOf(0))
var g = ArrayList<Int>(listOf(0))
val n = nextInt()
val coin = nextInts()
if (n != coin.size) throw Exception("input incorrect")
for(i in 1..100000) {
dp.add( coin.filter{it <= i}.map{dp[i-it]+1}.min() ?: 0 )
g.add( g[i-coin.filter{it <= i}.max()!!]+1 )
if (dp[i] != g[i]) {
println(i)
return
}
}
println(-1)
}
```
## Problem D -- Disrupting Defense
Problem setter: Min-Zheng Shieh
目標答對率設定為 50% ，做法並沒有用到什麼特殊的資料結構。但最終答對率僅約 28% ，出題者還要多學學。先觀察如果相同價值觀(value)的敵人超過半數，則不可能擊敗他們，因為你每次只能打倒兩個價值觀不同的，無法找到夠多跟他們價值觀相異的敵人來打倒他們。但如果相同價值觀的人沒有過半數，則每次選擇一個擁有在當下「人數最多」的價值觀。這種價值觀的敵人，必然有一個跟相異價值觀的人相臨。如果沒有，那根本就通通信仰同一價值，跟原先沒過半的假定矛盾。此時如隨便打倒一個此價值觀的敵人和另外一個人，則必然不會造成剩餘敵人中，具有某一價值觀的人超過半數(此部分證明略過)。因此能夠繼續執行這演算法，直到剩下兩個相異價值觀的敵人。因此最後一口氣打倒他們兩個，就完成攻略了。
時間複雜度：$O(n^2)$。因為 $n$ 次攻擊，每次攻擊先掃一次 $O(n)$ 統計價值觀，再掃一次 $O(n)$ 找最多的那種，最後再掃一次 $O(n)$ 找到該打倒的兩個敵人，並花至多 $O(n)$ 時間維護資料。
```kotlin=
private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}
fun main() {
val (n,k) = nextInts()
val a = nextInts().map{it-1}
var cnt = IntArray(k)
a.forEach{cnt[it] += 1}
if (n/2 < cnt.max()?:0) {
println(-1)
return
}
var used = BooleanArray(n)
for (rnd in 1..(n/2)) {
val m = cnt.max()!!
val t = cnt.indexOf(m)
val pos = a.mapIndexed{i, x -> if(x==t) i else -1}
.filter{it>=0 && !used[it]}
for (p in pos) {
var q = (p+1) % n
while (used[q]) q = (q+1) % n
if (a[q] != a[p]) {
used[q] = true
used[p] = true
cnt[t] -= 1
cnt[a[q]] -= 1
println("${p+1} ${q+1}")
break
}
}
}
}
```
## Problem E -- Explosion
Problem setter: Min-Zheng Shieh
目標答對率 <1% ，最終無人答對。對命題人而言是嘔心瀝血之作了，感謝最後試著解題的隊伍。這題作為難題，會要求隊伍需要具備特定知識：[最小包圓](http://mathworld.wolfram.com/MinimalEnclosingCircle.html)以及[凸包](https://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85)或極角排序。但以命題人的感受，這並不是特別難碰到的題材。
題目要炸掉一個半徑為 $r$ 的圓。除了一個選定點外，其餘所有點必須被該圓包覆，由範例測資可以確認摸到邊就算。
首先，先計算所有點的最小包圓。如果其半徑比 $r$ 小，那肯定有解。先直接假想炸在最小包圓的圓心上，然後選一個在最小包圓邊上的點，讓該點「倖免於難」：將圓心沿著該點往最小圓心的方向推，剛剛好推「超過」即可。
如果最小包圓半徑不比 $r$ 小，則需要排除一個點，也就是安全的點，之後重新計算最小包圓，看看是否不大於 $r$ 。如果不大於，那就找到一組解了。先觀察那些點可以做為這個安全點：只有最小包圓邊上的點才可以，不然最小包圓跟原來一樣，你不能炸，不是全滅就是炸完剩下兩個以上。
但問題是最小包圓上的點，可能有很多個，在本題我們選用的測試資料，最小包圓上可能有超過一千個點 (這就是為什麼產生了 Problem I 的原因)。可是其中其實只有至多三個點需要考慮：因為只有至多三個點，拿掉以後最小包圓會變小。
為何是三個？因為把最小包圓邊上的點拿來做凸包 (此時極角座標排序即可得到) ，這是一個圓內接多邊形。對應的圓周角如果不是銳角，拿掉也不影響最小包圓。但圓內接多邊形，至多只有三個角可以是銳角，也就是我們需要檢測的三個。
以下為範例程式碼：
```kotlin=
import java.math.BigInteger
import java.math.BigDecimal
import kotlin.random.Random
import kotlin.math.atan2
import java.util.TreeSet
private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}
data class BigFrac(val num: BigInteger, val den: BigInteger = BigInteger.ONE)
typealias Point = Pair<BigFrac, BigFrac>
val half = BigFrac(BigInteger.ONE, BigInteger.TWO)
fun BigFrac.conanical(): BigFrac {
val gcd = num.gcd(den)
if (den < BigInteger.ZERO)
return BigFrac(-num/gcd, -den/gcd)
return BigFrac(num/gcd, den/gcd)
}
operator fun BigFrac.unaryMinus() = BigFrac(-num, den)
operator fun BigFrac.plus(x: BigFrac): BigFrac =
BigFrac(num*x.den + den*x.num, den*x.den)//.conanical()
operator fun BigFrac.minus(x: BigFrac): BigFrac =
BigFrac(num*x.den - den*x.num, den*x.den)//.conanical()
operator fun BigFrac.times(x: BigFrac): BigFrac =
BigFrac(num*x.num, den*x.den)//.conanical()
operator fun BigFrac.div(x: BigFrac): BigFrac =
BigFrac(num*x.den, den*x.num)//.conanical()
operator fun BigFrac.compareTo(x: BigFrac): Int =
(this - x).num.compareTo(BigInteger.ZERO)
fun BigFrac.sqrt(scale: Int = 100): BigFrac {
val conan = conanical()
val (x, rx) = conan.num.sqrtAndRemainder()
val (y, ry) = conan.den.sqrtAndRemainder()
if (rx == BigInteger.ZERO && ry == BigInteger.ZERO)
return BigFrac(x, y)
val frac = toBigDecimal(scale*2).sqrt(java.math.MathContext.DECIMAL128)
val d = BigInteger.TEN.pow(frac.scale())
val n = (frac * d.toBigDecimal()).toBigInteger()
return BigFrac(n, d)
}
operator fun Point.plus(x: Point): Point =
Pair(first + x.first, second + x.second)
operator fun Point.minus(x: Point): Point =
Pair(first - x.first, second - x.second)
// inner product: %
operator fun Point.rem(x: Point): BigFrac =
first * x.first + second * x.second
infix fun Point.dot(x: Point): BigFrac =
first * x.first + second * x.second
// cross product: *
operator fun Point.times(x: Point): BigFrac =
first * x.second - second * x.first
infix fun Point.cross(x: Point): BigFrac =
first * x.second - second * x.first
// scalar product: BigFrac * Point
operator fun BigFrac.times(x: Point): Point =
Pair(this * x.first, this * x.second)
// scalar product: Point * BigFrac
operator fun Point.times(x: BigFrac): Point =
Pair(first * x, second * x)
fun Point.mag2(): BigFrac = this dot this
fun Point.mag(): BigFrac = mag2().sqrt()
fun BigInteger.toBigFrac() = BigFrac(this)
fun Int.toBigFrac() = this.toBigInteger().toBigFrac()
fun BigFrac.toBigDecimal(scale: Int = 80) =
BigDecimal(num, scale) / BigDecimal(den, scale)
fun BigFrac.toDouble() =
toBigDecimal().toDouble()
private fun nextFracs() = nextToks().map{it.toBigInteger().toBigFrac()}
fun ext(p: Point, q: Point, r: Point): Point {
val (x1, y1) = p
val (x2, y2) = q
val (x3, y3) = r
val m1 = p dot p
val m2 = q dot q
val m3 = r dot r
val num1 = m1 * y2 + m2 * y3 + m3 * y1 - y1 * m2 - y2 * m3 - y3 * m1
val num2 = x1 * m2 + x2 * m3 + x3 * m1 - m1 * x2 - m2 * x3 - m3 * x1
val den = x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1
return Pair(half * num1 / den, half * num2 / den)
}
fun center(pts: ArrayList<Point>, pass: Int, n: Int): Point {
if (pass == 3) return ext(pts[0], pts[1], pts[2])
if (n == 1) return pts[0]
var ret = half * (pts[0] + pts[1])
if (n == 2) return ret
var radius = half * (pts[0] - pts[1])
var dist2 = radius dot radius
for (i in 2 until n) {
val r = pts[i]-ret
if (dist2 < r dot r) {
pts[pass] = pts[i].also{pts[i] = pts[pass]}
ret = center(pts, pass+1, i+1)
radius = pts[0] - ret
dist2 = radius dot radius
}
}
return ret
}
fun nextPoints(n: Int): ArrayList<Point> {
var fracs: List<List<BigFrac>> = (1..n).map{nextFracs()}
return ArrayList<Point>(fracs.map{Point(it[0],it[1])})
}
fun BigFrac.toReadable(scale: Int = 10): String =
this.toBigDecimal(scale).toPlainString()
fun Point.toReadable(scale: Int = 10): String =
first.toReadable(scale) + " " + second.toReadable(scale)
class PolarCmp(val c: Point): Comparator<Point> {
override fun compare(a: Point, b: Point): Int {
val da = a - c
val db = b - c
val angleA = atan2(da.second.toDouble(), da.first.toDouble())
val angleB = atan2(db.second.toDouble(), db.first.toDouble())
return angleA.compareTo(angleB)
}
}
fun solve(pts: ArrayList<Point>, safe: Point, r2: BigFrac): String {
var n = pts.size - 1
val pos = pts.indexOf(safe)
pts[n] = pts[pos].also{pts[pos] = pts[n]}
var nc = center(pts, 0, n)
var nr2 = (nc - pts[0]).mag2()
if (nr2 > r2) return "-1"
return "${safe.first.num} ${safe.second.num}\n" +
"${nc.first.toReadable(20)} ${nc.second.toReadable(20)}"
}
fun main() {
val (n, _r) = nextInts()
val r = _r.toBigFrac()
var pts = nextPoints(n)
pts.shuffle()
var c = center(pts, 0, pts.size)
val radius = c - pts[0]
val r2 = radius dot radius
var ans = "-1"
if (r2 < r * r) {
val tune = 16
val epsilon = BigFrac(BigInteger.ONE,BigInteger.TEN.pow(tune))
val one = BigFrac(BigInteger.ONE)
c = c + (r/radius.mag()-one+epsilon) * radius
ans = "${pts[0].first.num} ${pts[0].second.num}\n" +
"${c.first.toReadable(tune*2)} ${c.second.toReadable(tune*2)}"
}
else {
val cand = TreeSet<Point>(PolarCmp(c))
pts.filter{val dx = it - c
val x2 = dx dot dx
x2 >= r2}.forEach{cand.add(it)}
for (p in cand) {
val s = cand.higher(p) ?: cand.first()
val t = cand.lower(p) ?: cand.last()
if (s - p dot t - p > BigInteger.ZERO.toBigFrac()) {
// at most 3 points pass this
val attemp = solve(pts, p, r*r)
if (attemp != "-1") {
ans = attemp
break
}
}
}
}
println(ans)
}
```
## Problem F -- Factorization
Problem setter: Yu-Hsuan Huang (NCTU_Teumessian)
目標答對率 10% ，主要考量是數論類的題目，台灣少出。最終答對率 5% ，或許大家的工具箱內還沒有這些裝備，要準備與國際隊伍競爭的同學，可以趁機補一下。當初命題者給了我一個完全超過我的數學知識的做法，因此我自己收到題目後先試著自己做做看。呃，給你兩數的積($b_0\cdot b_1$)還有和($b_0+b_1$)要你算出兩數 $b_0,b_1$ 為何？這不就想辦法算出兩數的差($b_0-b_1$)然後跟兩數的和拿來解方程式。因此，先想到的作法是 $\sqrt{(b_0+b_1)^2-4(b_0\cdot b_1)}$ 算出兩數的差，再回頭解 $b_0$ 跟 $b_1$。
因此問題就回到「在餘質數 $p$ 下開根號」了。大抵上這題在手上有 [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) 或是 [Cipolla](https://en.wikipedia.org/wiki/Cipolla%27s_algorithm) 這些演算法的隊伍，應該只要數學推一下後就毫無難度，頂多處理一下 $p=2$ 的特例。此外，由於開根號太針對性，我也認真想了一下，比較通用的方法是否能解。為此我們選了算出 $\mathbb{Z}_p^\times$ 的[原根 (primitive root)](https://en.wikipedia.org/wiki/Primitive_root_modulo_n)後，套用[離散對數(Discrete logarithm)](https://en.wikipedia.org/wiki/Discrete_logarithm)演算法，如[Baby-step Giant-step](https://en.wikipedia.org/wiki/Baby-step_giant-step)法來撰寫另解，確保時限內能夠讓此類算法通過。
## Problem G -- Gifted Bafuko
Problem setter: Sheng-Huei Chen (ICPC World Finalist, NCTU_Fox)
目標答對率 5% ，最終答對率約 1% ，意外變成王選試題。方法說穿了很簡單，就是找到一個 Leaf 之後，開始長樹，長不出去就砍掉重練，換一條邊再長一次，頂多三次。因為有唯一解，所以能長出來的只有一棵。
Leaf 如何找呢？由於題目上有限制點數 $n$ 至少 7 且 $G_T$ 所有節點 degree 至多 3，因此如果有一個點在 $G_U$ 的 degree 是 2，則它必然是一個 leaf 。如果都沒有結點 degree 是 $2$ ，那 degree 是 3 的必然是一個 leaf 。
長樹基本上就是修改 DFS，紀錄目前走進點的邊 ($u$,$v$) ，接下來檢查 $v$ 的 $G_U$ 鄰居中，有多少是 $u$ 在 $G_U$ 的鄰居，這些點才能是 $G_T$ 中 $v$ 的鄰居。並且還要是沒拜訪過、也不在 $u$ 在 $G_T$ 中的鄰居。這部分的檢查請大家自己推演一下。但如此我們就可以開始建構整棵樹了。
建構的過程中，如果一次長出超過 2 條邊，那就違背 degree 最多 3 的限制，可以直接停掉不長。如果到最後仍有點沒長出來，則這也不是我們要的答案。
```kotlin=
private fun nextLine() = readLine()!!
private fun nextInt() = nextLine().toInt()
private fun nextToks() = nextLine().split(" ")
private fun nextInts() = nextToks().map{it.toInt()}
fun dfs(u: Int, v: Int, adj: ArrayList<IntArray>,
ans: Array<ArrayList<Int>>, visited: BooleanArray): Int {
var ret = 1
visited[v] = true
val cand = adj[v].filter{!visited[it] && u in adj[it] && it !in ans[u]}
if (cand.size>2) return -1
ans[v].add(u)
ans[v].addAll(cand)
ans[v].sort()
for (w in cand)
ret += dfs(v, w, adj, ans, visited)
return ret
}
fun solve() {
val n = nextInt()
var adj = ArrayList<IntArray>()
var leaf = -1
var cap = 3
var buf = StringBuilder()
for (v in 1..n) {
adj.add(nextInts().drop(1).map{it-1}.toIntArray())
if (adj.last().size <= cap) {
leaf = v-1
cap = adj.last().size
}
}
for (v in adj[leaf]) {
var ans = Array<ArrayList<Int>>(n){ArrayList<Int>()}
var visited = BooleanArray(n){it==leaf}
ans[leaf].add(v)
val size = dfs(leaf, v, adj, ans, visited)
if (size == n-1) {
for (lst in ans)
buf.append("${lst.size} ${lst.map{it+1}.joinToString(" ")}\n")
break
}
}
print(buf)
}
fun main() = (1..nextInt()).forEach{solve()}
```
## Problem H -- Hotel
Problem setter: Hsin-Chen Chuang (ICPC World Finalist, NCTU_Fox)
目標答對率 15% ，結果約 7%。有點驚嚇的低答對率。這是一題單點更新、區間查詢線段樹就可以做的題目。線段樹確實對中階以及中階之下的隊伍來說，是一個未必有接觸的題材。但中前段隊伍怎麼可能不會線段樹？因此答對率這麼低，出乎意料。
線段樹是一種資料結構，用來儲存一個序列: $a_1,\cdots,a_n$，而序列元素的資料型態，可以進行具備結合律的運算 $\oplus$，線段樹可提供快速 ($O(\log n)$) 的計算出任一個連續片段 $a_\ell\oplus a_{\ell+1} \oplus \cdots \oplus a_r$ 的值，並且提供快速 ($O(\log n)$) 更新序列中單一元素。在某些特定情況下，也能夠用一些技法達到快速 ($O(\log n)$) 的區間修改操作。常見的例子有，拿來求整數數列的片段最大值、最小值、總和等等，因為這些操作 ($\max$, $\min$, $+$) 都具備結合律。
本題首先要利用高度變化時，不會發生與相鄰高度一樣的保證。將實際上表示的序列改成 $d_i = h_{i+1} - h_i$ 。則原問題變成是在詢問， $d_\ell,\ldots,d_{r-1}$ 中，最長的一段「正負號至多換一次，且先正後負」的最長片段長度。由此我們開始定義一個資料型態 `Seg(size, b, e, ans, ba, ea)` ，其中 size 代表這個資料是對應到多長的序列片段，b代表片段開頭的序列元素，e代表片段結尾的序列元素，ans代表這個片段的最佳解，ba 代表從開頭開始的片段之「正負號至多換一次，且先正後負」最長長度，ea則代表從結尾往前的片段之「正負號至多換一次，且先正後負」最長長度。而這種新資料，我們定義將其相接的操作為 `concat` ，而這個操作是具備有結合律的，更新時沿路重算即可。剩下的事情，我們就交給線段樹了，請參考下述參考程式碼。
```kotlin=
private fun nextLine() = readLine()!!
private fun nextToks() = nextLine().split(" ")
private fun nextInt() = nextLine().toInt()
private fun nextInts() = nextToks().map{it.toInt()}
data class Seg(val size: Int = 0, var b: Int = 1, var e: Int = 1,
val ans: Int = 1, val ba: Int = 1, val ea: Int = 1)
infix fun Seg.concat(x: Seg): Seg {
val sz = size + x.size
val ok = e > 0 || x.b < 0
var newBA = if (ba == size && ok) ba+x.ba else ba
var newEA = if (x.ea == x.size && ok) ea+x.ea else x.ea
val best = maxOf(ans, x.ans, if(ok) ea+x.ba else 0)
return Seg(sz, b, x.e, best, newBA, newEA)
}
const val H = 18
var t = Array<ArrayList<Seg>>(H){ArrayList<Seg>()}
fun update(pos: Int, d: Int) {
if (pos < 0 || pos >= t[0].size) return
t[0][pos].b += d
t[0][pos].e += d
for (h in 1 until H) {
val q = pos shr h
if (q >= t[h].size) break
t[h][q] = t[h-1][2*q] concat t[h-1][2*q+1]
}
}
fun query(h: Int, L: Int, R: Int): Seg {
if (L==R-1) return t[0][L]
val ls = L.shr(h-1)
val rs = (R-1).shr(h-1)
if (ls==rs) return query(h-1, L, R)
if (R==L+1.shl(h)) return t[h][L.shr(h)]
val M = rs.shl(h-1)
return query(h-1, L, M) concat query(h-1, M, R)
}
fun query(L: Int, R: Int): Int {
if (L==R) return 1
if (L+1==R) return 2
return query(H-1, L, R).ans + 1
}
fun solve() {
val n = nextInt()
var seq = nextInts()
var buf = ArrayList<String>()
for (x in t) x.clear()
for (i in 1 until n)
t[0].add(Seg(1, seq[i]-seq[i-1], seq[i]-seq[i-1]))
for (i in 1 until H)
for (j in 0 until t[i-1].size-1 step 2)
t[i].add(t[i-1][j] concat t[i-1][j+1])
val q = nextInt()
for (i in 1..q) {
val (op, L, R) = nextInts()
if (op == 1) {
update(L-1,R)
update(L,-R)
}
else buf.add("${query(L,R)}")
}
println(buf.joinToString("\n"))
}
fun main() = (1..nextInt()).forEach{solve()}
```
## Problem I -- Integral Points
Problem setter: Min-Zheng Shieh
目標答對率 30% ，最終答對率約 16% 。這一題是 Problem E 準備測試資料過程時的副產品。事前很難估難度，因為出題者也不知道怎樣做才能及時做完，只想藉機宣揚本地打表這項技法，畢竟月球表面可以放很多東西。能夠成為答案的半徑，應該多能寫成 $k(n^2+m^2)$ 這種形式，請參考[畢氏三元數](https://en.wikipedia.org/wiki/Pythagorean_triple)，找一些很多組$k$, $m$ 跟 $n$ 產生出重複的來試，然後暴力檢查有多少個 Integral Points。我希望當初驗題的吳宗達可以提供他的想法，因為他寫了一個沒有在本地作業的程式碼並在時限內通過。
範例程式是事前先找出一個 $r$ ，然後認真的把圓上所有整數點給找出來，再印出答案。
```kotlin=
fun main() {
val n = readLine()!!.toInt()
val r = 5928325L
val r2 = r*r
var squares = ArrayList<Long>()
var output = HashSet<Pair<Long,Long>>()
for (i in 0L..r) {
val q = i*i
val p = r2 - q
squares.add(q)
val j = squares.binarySearch(p).toLong()
if (j >= 0) {
output.add(Pair(i, j))
output.add(Pair(j, i))
output.add(Pair(-i, j))
output.add(Pair(-j, i))
output.add(Pair(i, -j))
output.add(Pair(j, -i))
output.add(Pair(-i, -j))
output.add(Pair(-j, -i))
}
if (output.size >= n) break
}
println(r)
output.take(n).forEach{println("${it.first} ${it.second}")}
}
```
Sign in with Wallet
Connect another wallet