給一個大整數 $N \le 2^{54}$，判斷是否為質數，若不是則進行因數分解，並且輸出最小的質因數。
備註：大整數分解不可使用一般的 $O(\sqrt{N})$ 算法完成。
|
|
|
|
以下的寫法還不是最快的，而且沒有加上最小質因數的剪枝。若在 pollard-rho 算法中，使用 Brent’s algorithm 取代 Floyd’s algorithm 進行環偵測，同時減少模數使用會變得更快 (常數上)。
討論區提供卡邁克爾數 (Carmichael Number)，讓費馬素性檢驗 (Fermat primality test) 判斷失誤，若用盧卡斯-萊默檢驗法 (Miller–Rabin primality test) 則不受影響。這讓我想到寫過鄒賽爾數 (Zeisel Number) 生成，由數個質數構成大數 $N$ 能測試更多的效能瓶頸吧。
|
|
給一堆平行兩軸的矩形，請問面積的聯集為何。
|
|
|
|
利用掃描線算法，從 x 軸小掃描到大，維度 y 軸上的覆蓋情況。
若單純用離散方法在 2D 網格上填充，算法複雜度是 $O(n^2)$，最慘情況還會再增加到 $O(n^4)$，平均上來說離散方法是可行，但是記憶體是 $O(n^2)$。
由於 ITSA 的那題 n 會高達 30000，於是拿這一題來練手，掃描線算法複雜度 $O(n \log n)$，利用線段樹操作時，維護某個區間的完全覆蓋數，當完全覆蓋數等於 0 時，則計算子樹的覆蓋長度總和，雖然沒辦法完全覆蓋，則部分覆蓋可以從子樹計算得到。
|
|
|
|
(Figure 1)
There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o’clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90’ (degrees) clockwise on those clocks which are affected according to figure 2 below.
| Move | Affected clocks |
|---|---|
| 1 | ABDE |
| 2 | ABC |
| 3 | BCEF |
| 4 | ADG |
| 5 | BDEFH |
| 6 | CFI |
| 7 | DEGH |
| 8 | GHI |
| 9 | EFHI |
(Figure 2)
Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o’clock, 1=3 o’clock, 2=6 o’clock, 3=9 o’clock.
Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o’clock. You are convinced that the answer is unique.
|
|
|
|
原來之前寫過這一題，請參閱 d730: 升旗典礼 ——加强版
用 BFS 從 0 0 0 0 0 0 0 0 0 開始倒推回去，在 mark 的部份，用 4 進制 bitmask。
這題在 POJ 似乎只有一組測資，在 Zerojudge 則有非常多筆測資。
而事實上網路上還有另外一個高斯消去法，先預求反矩陣，之後直接帶入計算即可。沒有仔細去研究，不過聽說那解法限定一定有合法解，如何判定不合法解又是另外一個問題。總之，用了 BFS 過了就沒仔細去探討其他解法。
|
|