今天來聊聊四種解題方法之一：枚舉法。每一道題目都有一個解，當我們沒辦法立刻說出答案的時候，最原始的方法就是利用試誤(trial-error)的原則，考慮所有可能的答案，並一個一個判斷是否它滿足我們的需求。有時候這方法挺好用的。
資訊與數學最大的不同是，我們可以利用有限的時間，讓電腦幫我們逐一檢驗可能的答案，進而省略一些繁雜的數學證明或更細緻的檢驗步驟。
換句話說，如果我們能用簡單的數學證明保證答案會出現在我們提出的許多數值之中，那麼就能夠證明演算法的正確性了。
例題 1：判斷質數
顯然，要「否定」$n$ 是否為質數這個敘述，只需要找出一個「反例」。而顯然這個反例 $x$ 會介於 $[2, n-1]$ 之間。逐一檢查 $2, 3, \ldots, n-1$ 就可以知道答案是 Yes 還是 No 了。這個方法需要 $O(n)$ 次模運算。
透過簡單觀察，我們發現：若 $n$ 是合數，可以表示成 $n=a\times b$。那麼此時有 $\min(a, b)\le \sqrt{n}$。也就是說，若存在反例，最小的反例一定會出現在 $[2, \sqrt{n}]$ 之間。於是，我 們就得到一個 $O(\sqrt{n})$ 時間的演算法了。
參考程式碼
bool isprime(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
結論
例題 2：[LC326] Power of Three
注意到 3 的次方其實數量不多，所以我們可以直接嘗試所有可能的次方數值，並且與 $x$ 進行比對。
參考程式碼
bool isPowerOfThree(int n) {
for (long long i = 1; i <= n; i *= 3)
if (n == i)
return true;
return false;
}
結論
延伸思考
這題其實不使用諸如 log() 函式的浮點數計算也可以做得到 $O(1)$ 時間唷，你能想得到嗎？
例題 3：[CF233B] Non-square Equation
對於一個一元二次方程我們可以利用已知的公式 $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$ 來求出方程的根，但是 $s(x)$ 是一個與 $x$ 有關的函數，所以無法直接從公式下手。枚舉 $x$ 的範圍可以粗估是 $1\le x\le \sqrt{n} \approx 10^9$，但一個一個檢查會花太多時間。
注意到 $s(x)$ 是 $x$ 的各位數字和，這個值的範圍相較於 $n$ 小了不少。可以估計的是當 $x\le 10^{9}$ 時，有 $1\le s(x)\le 81$。因此若我們先逐一枚舉 $s(x)$ 的值，就可以把題目當成一般的一元二次方程來解了！找到解以後，再驗證其各位數字和是否就是我們枚舉的值，就可以了。
參考程式碼
#include <iostream>
#include <cmath>
using namespace std;
// 計算各位數字和。
int s(long long x) {
int t=0;
while(x>0) { t+=x%10; x/=10; }
return t;
}
// 對於枚舉的 s(x) 值 t，找出合法的解，由於解會是一正一負，我們只回傳正的那個。
long long getsol(int t, long long n) {
long long r = t*t+n*4, v = 0;
v = sqrt(r);
while(v*v<r) v++; while(v*v>r) v--;
if(v*v!=r) return -1;
v-=t; if(v%2 || v<0) return -1;
v/=2;
return v;
}
int main(void) {
long long n, x, t, ans=-1;
cin >> n;
for (t = 1; t <= 81; t++) {
x = getsol(t, n);
if(x<0) continue;
if(s(x)==t && ( ans==-1 || ans > x)) ans = x;
}
cout << ans << endl;
return 0;
}
結論
練習題
- [URAL1854] Negotiations with Parthians 古希臘以及古羅馬人不喜歡偶數。現在 Andrian 有 $n$ $(1\le n\le 10^{18}-1)$ 隻羊(奇數隻)要獻給神明，為了公平，每一位神明都要得到數量相同的羊。為了更吉利，Andrian 決定將羊群獻給奇數位神明、並且這個數量也要有奇數個正因數。請問 Andrian 至多可以將羊獻給多少位神明呢？
- [CF911C] Three Garlands Mishka 買了三個聖誕樹的裝飾燈品，第 $i$ 個燈從開啟的那一剎那每間隔 $k_i$ 秒就會亮燈一下 $(1\le k_i\le 1500)$。Mishka 想知道是否存在三個開啟燈泡的時間 $x_1, x_2, x_3$，使得三個燈都打開以後，每一秒鐘都至少有一個燈泡亮著？
- [CF233B] Non-square Equation 有一個長 $10^5$ 公分、高 $100$ 公分的木頭箱子，箱子下方與上方各有一些水平擺放的鏡子、以及箱子左右兩端分別有一個可以讓光線進入的小孔，分別在高度 $h_l$ 以及 $h_r$ 公分處。下面的圖表示了箱子的情形：  在遊戲中，你必須要從左方的小孔中發射一束雷射光，然後讓這束光從右方小孔鑽出。每一面鏡子都有一個分數 ，若射中該面鏡子，則得到對應之分數。為了增加遊戲的趣味性，規定**雷射光只能打到每一面鏡子至多一次**。請找出最高的可能得分。鏡子數 $0\le n\le 100$。保證輸入的 鏡子位置彼此不會重疊。
- [ECNA2018B] Difference 小差距序列(SDS) 是一個由正整數定義而成的序列。它的描述如下：首項 $A_1$ 為一個正整數 $r\ge 1$。對於 $n>1$，定義 $A_n = A_{n-1}+d$，其中 $d$ 是最小的正整數，使得對於任意 $1\le i<j<n$，$d\neq A_j-A_i$。此外 $d$ 也不能等於任意一個當前數列的值。給定 $r$ 以及 $m$ 值($1\le r \le 100, 1\le m\le 200000000$)，請找出最小的 $n$ 使得要嘛 $m=A_n$，或者 $m$ 是兩個 $\set{A_1, \ldots, A_n}$ 的數字差。