| Event | 演算法競賽與題目分享（ 質因數分解應用 ）

嗨，又是我話很多但程式碼短的 Leo

（ 閒話家常一下，想直接看演算法可以往下拉到題目介紹 ）

在進入 42 以後，偶爾會有些線上的演算法競賽，讓我們自由報名並與全法國的學生及工程師一起競爭。一方面在限定的時間內腦力激盪挑戰打字速度極限蠻有趣的，另一方面成績好通常有獎品，所以時間允許的話我都一定參加。

目前，我共參加了兩次，分別是今年 6 月的 BattleDev 還有 10 月剛結束，由 Le Shaker 舉辦的 La Coding Battle ，兩次的競賽規則一樣，共有 2 小時， 6 道題按照順序來解，卡住也沒辦法先往後看。特別的是得使用他提供的線上 IDE 傳 code ，沒有辦法自訂測資來測試只能直接 submit 跑他完整的測資，但答錯並無 penalty，還有從競賽開始後就不能再更改自己使用的程式語言，算是讓我感受到了文化差異。

第一場比較沒有好題，前五題太水（ 知識點單一且都是經典演算法 ），而第六題題目很冗（ 印象中至少 6 頁吧 ，再加上英文版還有寫錯，我一小時根本讀不完 QQ ），又沒特殊知識點，所以就不特別介紹了。

最後我排在第 18 名，是 42 校內第一，還因此在我的 42 intra 獲得了 algo boy 的稱號。

第二場題目設計就比較恰當，前三題都很簡單（ 不用任何演算法知識大概也能寫出來 ），而第四題敘述蠻奇怪的，看起來像是要找周長最小的凸包，我亂 submit 了幾次後才通靈出題目的意思。但這題真的槽點太多，明明照他給的測資範圍該是 O( H * log ( H ) ) 演算法才能過，但我亂傳個 O( H² ) 就水過去，總之這題算是這次比賽我最不滿意的一題。

第五題是給定我們一棵樹，然後要把其中一些節點塗色，規定每個塗色節點只能與最多一個塗色節點相鄰，問最多能塗幾個點，大家可以想想該怎麼做。

至於第六題，題目的範例輸出竟然寫錯，蠻雷的，但等等還是值得我好好講一講這題。

總之這次拿了第 7 名，前 5 名有現金，從那之後就只有禮券，所以我得來好好練練打字了，看看下次名次能不能再好一些…

題目介紹

那現在就來講第六題吧，原題目有點長但我把他濃縮了

題目敘述

給定一正整數 V ，求有多少種邊長皆為整數的矩形的面積加上周長等於 V（ 長寬互換仍當同一種矩形 ）

其中 V ≤ 10¹⁵

範例

input = 20

output = 2

說明

當 V = 20 時，我們能找到長寬分別為 （ 6 , 1 ）和（ 4 , 2 ）的長方形，所以共有兩組滿足條件

長寬為 6 , 1 的矩形面積為 6* 1= 6 ，周長為 2 * ( 6 + 1 ) = 14 ，6 + 14 = 20 ，長寬為 4 , 2的矩形則有面積 4 * 2= 8 和周長 2 * ( 4 + 2 ) = 12 ， 8 + 12 = 20 ，所以可以驗證這兩組解確實符合條件

相信題目已經清楚了，大家不想被暴雷的話先暫停想一下，迫不及待的同學則可以直接往下…

解題過程

首先，我們假設矩形的寬為 a , 長為 b ，那麼矩形的面積就是 ab , 周長為 2 ( a + b ) ，所以我們可以把題目簡化成計算共有幾組整數對 ( a , b ) 滿足 V = ab + 2 ( a + b ) 且 1 ≤ a ≤ b， 事先設定好 a , b 的大小關係可以避免 ( 1 , 2 ) , ( 2 , 1 ) 這種長寬互換的情形被重複算到

接著就可以使用數學小技巧：

V = ab + 2 ( a + b )

V = ab + 2a + 2b

V + 4 = ab + 2a + 2b + 4 = ( a + 2 ) ( b + 2 )

有了 V + 4 = ( a + 2 ) ( b + 2 ) 這個條件，現在只要將 V + 4 的因數找出來，就能計算出有多少組滿足條件的 ( a , b ) 數對了

我們先使用較小的數字來實做一次，假設 V = 20，那麼 V + 4 = 24

24 的因數共有 1, 2, 3, 4, 6, 8, 12, 24

其中我們能把各因數兩兩配對，就會變成

24 = 1 * 24 = 2 * 12 = 3 * 8 = 4 * 6

那麼會發現 ( a + 2 , b + 2 ) = ( 1 , 24 ) , ( 2 , 12 ) , ( 3 , 8 ) , ( 4 , 6 )

( a , b ) = ( -1 , 22 ) , ( 0 , 10 ) , ( 1 , 6 ) , ( 2 , 4 )

前兩組因為 a 不是正整數，所以不合，因此總共有兩組數對 ( a , b ) 滿足條件，答案為 2

從這過程中我們可以看到：只要先將 V + 4 的因數寫出來，兩兩配對，把 a + 2 = 1 和 a + 2 = 2 的情況扣掉，剩下幾組就是我們要的答案了

這個結論大致正確，只要注意唯一的例外情況：V + 4 有奇數個因數

只有在 V + 4 為完全平方數時才會有奇數個因數，所以在兩兩配對這一步驟，會留下最中間的數，讓他跟自己配對，像是 36 有 1 , 2 , 3 , 4 , 6 , 9 , 12 , 18 , 36

36 = 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6

也就是說，在 V + 4 有奇數個因數時，會有一個因數跟自己配對

那麼在觀察了這些規律後，我們的解題策略變成：

1. 算出 V + 4 的因數個數 k
2. 若 k 為偶數，則 ( a + 2 , b + 2 ) 數對共有 k / 2 組 ， 若 k 為奇數則有 ( k + 1 ) / 2 組
3. 將 a ≤ 0 ，也就是 ( a + 2 ≤ 2 ) 數對給扣掉，剩餘即為所求

現在，我們只需要一個快速算出 V + 4 因數個數的方法，這就回到我們這篇文章的大標題了：質因數分解

所謂質因數分解，就是將一個數 x 化成 (p[0]^q[0]) * (p[1]^q[1]) * … * (p[n]^q[n]) 的形式，其中 p[i] 為 x 的質因數，符號 ^ 代表次方

舉例來說，我們可以將數字 24 分解成 24= 2³ * 3¹

那麼這跟因數個數有什麼關係呢？以剛剛的 24 為例，我們可以發現他的因數都可以寫成 (2^i ) * (3^j ) 這種形式，而且 0 ≤ i ≤ 3 , 0 ≤ j ≤ 1，像是 6 = 2¹ * 3¹ , 12 = 2² * 3¹, 8 = 2³ * 3⁰ , … ，所以只要算出有幾對符合條件的 ( i , j ) 就知道有幾個因數了。以 24 = 2³ * 3¹ 來說，因為 i = 0 , 1 , 2 , 3 有這 4 種可能性，j = 0 , 1 有 2 種可能，因此因數個數就是 4 * 2 = 8 個。

總之，質因數分解將數字 x 化成 (p[0]^q[0]) * (p[1]^q[1]) * … * (p[n]^q[n]) 的形式後，能直接算出因數數量為 ( q[0] + 1 ) * ( q[1] + 1 ) * … * ( q[n] + 1 )

現在我們會算因數個數了，那就能解這題了，我也提供 C++ 程式碼給同學們參考一下

一開始的前置作業， 主要都是為了實做方便

typedef long long ll;
V += 4;
bool divisible_by_1 = (V % 1 == 0);
bool divisible_by_2 = (V % 2 == 0);

1. 質因數分解，這裡可以使用 unordered_map ，實做方便

unordered_map<ll,ll> prime_factor; // prime_factor[p] = q 表示 p^q 能整除 V
for (ll i = 2 ; i * i <= V ; ++i)
    while (V % i == 0) {
        ++prime_factor_power[i];
        V /= i;
    }
if (V > 1) // 最後除剩下的如果非1，就是最後一個質因數
    ++prime_factor_power[V];

2. 由質因數分解的結果來計算因數個數

ll factors_amount = 1; 
for (auto it = prime_factor.begin();it != prime_factor.end();++it)
    factor_amount *= it->second + 1;

3. 將因數兩兩配對，也就是算有幾對 ( a + 2 , b + 2 ) 滿足 ( a + 2 ) ( b + 2 ) = V + 4

ll factor_pair_amount;
if (factor_amount % 2 == 0) {
    factor_pair_amount = factor_amount / 2;
}
else {
    factor_pair_amount = (factor_amount + 1) / 2;
}

4. 扣掉 a + 2 ≤ 2 的可能性：如果 V + 4 能被 1 整除，那我們先前算到的因數對就有 ( 1 , V + 4 ) ，必須扣掉，若能被 2 整除則必須扣掉 ( 2 , ( V + 4 ) / 2)

ll answer = factor_pair_amount;
if (divisible_by_1)
    --answer;
if (divisible_by_2)
    --answer;
if (answer < 0)
    answer = 0; // 答案不可能為負數

這樣就成功算出 answer 了

最後附上我在賽中的 AC code

typedef long long ll;
ll solve(ll V) {
    V += 4;
    
    ll is_even = 1 - V % 2; 
    
    unordered_map<ll,ll> prime;
    for (ll i = 2 ; i * i <= V ; ++i)
        while (V % i == 0) {
            ++prime[i];
            V /= i;
        }
    if (V > 1)
        ++prime[V];
    
    ll ans = 1;
    for(auto it = prime.begin() ; it != prime.end() ; ++it) 
        ans *= it->second + 1;
    
    return (ans - 1) / 2 - is_even;
}

大概就這樣，如果有哪裡講不夠清楚的可以留言跟我說