# 更聰明的暴力法

同樣是暴力法，做得聰不聰明，可能會大大地影響執行效率。
暴力的優化沒什麼固定的模式可循，在此挑幾個常見的進行介紹。

## 省略不必要的計算

例如以下問題：

:::success
### 質數？不是質數？

輸入一個正整數 $N$ 回答 $N$ 是不是質數。

$N \le 2,147,483,647$

#### 範例輸入

2147483647

#### 範例輸出

YES

#### 範例輸入

1073741824

#### 範例輸出

NO

:::

若要窮舉所有比 $N$ 小的正整數，複雜度 $O(N)$ 顯然計算量過大。
不過觀察可以發現，若 $N$ 存在一因數 $K$，表示 $N$ 被 $K$ 整除；
這代表 $N \div K$ 也是正整數，可知因數是成對存在的。

例如 $12$，窮舉到 $2$ 同時可得到 $12\div 2 = 6$，
使得 $6$ 早因成對的 $2$ 被窮舉過，導致重覆而顯得毫無意義。
因此，$6$ 是屬於不需要窮舉也不影響結果的部份。

由上可知，窮舉所有 $K$ 使得 $N\div K \ge K$ 即可。
移項可知只需窮舉所有 $K$ 滿足 $K^2 \le N$ 就足夠了。

如此複雜度可降為 $O(\sqrt{N})$ 大約是 $46340$ 左右的窮舉量，
落在可接受的合理範圍。

當然，如果你學會快速建質數表的方法，
只窮舉 $46340$ 以內的質數可以更進一步降低運算量，
不過必須先付出找質數的代價。

:::success
### UVa 541 - Error Correction
http://domen111.github.io/UVa-Easy-Viewer/?541
:::

這題雖可窮舉改變每個位元，共有 $O(N^2)$ 個位元需要嘗試，
每次嘗試需要 $O(N)$ 的複雜度驗證，可得到 $O(N^3)$ 的做法。

觀察可發現改變 $1$ 個位元，只能夠影響 $1$ 行或 $1$ 列。
也就是說，存在 $2$ 行或 $2$ 列以上總和並非偶數時肯定救不回來，
此時窮舉也只是浪費時間。

且改變 $1$ 個位元將同時影響其所在的行與列，
因此必須在行和列都恰有 $1$ 個總和是奇數時，改變才會有效。

如此一來，找出改變點只需窮舉每行每列，找出總和為奇數的數量和位置即可，
複雜度降為 $O(N)$。

計算每行每列需窮舉每個點，複雜度為 $O(N^2)$ 還比找改變點的計算量大；
最後可得總複雜度 $O(N^2+N) = O(N^2)$。

## 迴避重覆計算，共用結果

有些題目仔細觀察，會發現每次計算的東西有一部份是重覆、共通的。
找出共通的部份，可以避免無謂的重覆計算。

:::success
### UVa 498 - Polly the Polynomial
http://domen111.github.io/UVa-Easy-Viewer/?498
:::

單獨計算每一項，則最高 $N$ 次時會有 $O(N)$ 項，
每項需要 $O(N)$ 次乘法以計算 $x^N$，複雜度是 $O(N^2)$。

觀察發現 $x^N = x^{N-1} \times x$，只差一次乘法，
而且 $x^{N-1}$ 在 $N-1$ 次項也是得算一遍，那不如先算完 $N-1$ 次項之後，
用 $N-1$ 次項的結果來算 $N$ 次項，就只需要一次的乘法。

將順序改為從常數項開始，第 $K$ 項的 $x^K$ 由前一項算過的 $x^{K-1}$ 乘上 $x$ 算出，
則每項只要 $O(1)$ 的計算量，總複雜度為 $O(N)$。

:::warning
本題的 IO 處理較為複雜，可參考 [善用 sstream](/NX46vl9lSN2bCABECaoVEg) 會輕鬆許多。
:::

:::success
### UVa 11059 - Maximum Product
http://domen111.github.io/UVa-Easy-Viewer/?11059
:::

任意連續段 $S_i, S_{i+1}, ..., S_{j-1}, S_j$ 都會是以數字 $i$ 為起點、數字 $j$ 為終點的形式；
窮舉所有數對 $(i, j)$ 滿足 $i \le j$，令 $i$ 為起點、$j$ 為終點，
即可找出所有連續段。

數對共 $O(N^2)$ 個，每個數對將 $i$ 到 $j$ 所有數字相乘需 $O(N)$ 次乘法，
總複雜度為 $O(N^3)$。

不過考慮 $(i, j) = S_i, ..., S_{j-1}, S_j$
把 $S_j$ 遮掉不看的話，會剩下 $S_i, ..., S_{j-1}$，剛好是連續段 $(i, j-1)$

也就是說，以 $i$ 為起點到以 $j-1$ 為終點的連續段，
和以 $i$ 為起點到以 $j$ 為終點的連續段，只差了一個 $S_j$，
其它都是完全一樣的。

例如從第 $2$ 個數字到第 $5$ 個數字，和從第 $2$ 個數字到第 $6$ 個數字，
除了後者多了第 $6$ 個數字外，其它完全相同。

因此，若在固定起點 $i$ 時，令 $j$ 由小到大按順序計算，
則 $(i, j)$ 連續段的乘積，可由上一段 $(i, j-1)$ 的乘積，再乘上 $S_j$ 求得，
每一段只需一次乘法。

共有 $O(N)$ 個起點，每個起點最多 $O(N)$ 個終點，
每段連續段取用上個連續段的計算結果，只需 $O(1)$ 的計算量，總複雜度 $O(N^2)$。

## 歡樂練習時間

:::info
除了寫出程式碼，一邊練習看看，分析你的解法複雜度是多少？
:::

:::danger
注意：自二章起，練習題不再依難易度與前置關係排序，請閱讀題目後自力判斷。

另，由於題目排列順序不具任何意義，無需自第一題做起。卡住時可先嘗試其他題目，累積實力再回來看，或許就能順利解出。
:::

:::success
### Kattis averageshard - Paradox With Averages (Hard)
https://open.kattis.com/problems/averageshard

目標 O(N)

:::

:::success
### Kattis fluortanten - Fluortanten
https://open.kattis.com/problems/fluortanten

目標 O(N)

:::

:::success
### ZJ b840 - 104北二4.農作物採收問題
https://zerojudge.tw/ShowProblem?problemid=b840

目標 O(N^4)
（雖然有 O(N^3) 的做法，不過目前缺乏前置知識）

:::

{%hackmd @sa072686/__style %}

###### tags: `競程：二章`, `競程`