Re: [閒聊] LeetCode Biweekly Contest 96

作者: fxfxxxfxx (愛麗絲)   2023-01-22 00:26:07
※ 引述《fxfxxxfxx (愛麗絲)》之銘言:
: 4. Check if Point Is Reachable
: 花了 10 秒丟一個 return gcd(x, y) == 1 試試
: 果不其然是錯的
: 想了一陣子之後,發現幾個性質
: 1. 不能讓值變成 <= 0,不然永遠回不去,因為無法讓另一個也變負的
: 2. 因此想讓值變大只能用 *2 的
: 3. 因此對 (X, Y) 而言,假如 X = 2 * Z
: 則 (X, Y) 是否能到達若且唯若 (Z, Y)
: 4. 因此我們可以等價的轉換成都是奇數的形式
: 5. 如果都是奇數且不失一般性令 X >= Y,則
: (X, Y) 能否到達等價於 (X - Y, Y) 能否到達
: 不能減另一個方向因為會讓其中一邊 <= 0
: 所以可以讓 (X, Y) 不斷遞減,
: 且每兩次操作至少減半一次(第5步的 X-Y 一定是偶數)
: 所以是 O(logn) 可以解
看了別人的解才發現
最後那個X 和 Y 互減
其實根本就是在做 gcd (加速版,因為遇到偶數會除2)
所以這題其實是在問公因數是否只有 2 (或沒有)
要炫技的話可以用
return __builtin_popcount(gcd(targetX, targetY)) == 1;
來一行解決 = =

Links booklink

Contact Us: admin [ a t ] ucptt.com