【C++】競程筆記（數學&程式設計）
===

[TOC]

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

---

質數（prime numbers）與因數（factor）
---

因數定義：「 $y$ 是 $x$ 的因數代表 $x$ 除以 $y$ 為整數」。

在程式設計上則以 `x % y == 0` 表示。

// from NTUCPC Guide
for (int y = 1; y <= x; y++) {
    if (x % y == 0) {
        // y 是 x 的因數
    }
}

這樣 for 迴圈的遍歷方式，時間複雜度為 $O(x)$ ，因為有 x 個元素要判斷。

而在我們正常尋找因數的方法，如下：

$12 = 1 \times 12 = 2 \times 6 = 3 \times 4 = 4 \times 3 = 6 \times 2 = 12 \times 1$

可以發現，當因數 $>3$ 時，後面的因數與前面完全一致，我們到 $3$ 的時候就不會繼續找因數了。

為了要優化上面的代碼，所以可以透過這一個特性，避免重複計算，進而提升速度：

// from NTUCPC Guide
for (int y = 1; y * y <= x; y++) {
    if (x % y == 0) { // x = y * (x / y)
        // y 是 x 的因數
        // x / y 是 x 的因數
        // y 跟 x / y 可能是相同的，如果不能重複處理的話要特別注意
    }
}

因為只要滿足 $y \leq \frac{x}{y}$ ， $y^{2} \leq x$ 這個條件即可。

那這樣就可以將時間複雜度降為 $O(\sqrt x)$ 了。

> 不要把 `y * y <= x` 寫成 `y <= sqrt(x)`，因為 `sqrt(x)` 的結果是浮點數，可能會有浮點數誤差。

而至於質數部分，具體程式碼實現如下：

// from NTUCPC Guide
bool is_prime(int x) {
    for (int y = 2; y * y <= x; y++) { // 起始值是 2
        if (x % y == 0) { // x = y * (x / y)
            return false;
        }
    }
    return true;
}

大數四則運算
---

因為 C++ 的資料型態都設有一定的範圍限制，所以在做一些「大數」運算的時候，難免會出現 overflow 的問題，因此就要自己手刻運算程式。

### 儲存大數
---

利用陣列儲存每一個數字的位數：

int a[len] = {1,2,3,4,5,6,7,8,9}; // 123456789
int b[len] = {3,2,7,1,2,6,5,4,9,0,9,0,0,1,1,2,2,3,4,2,7,5}; // 3271265490900112234275

### 加法
---

兩數相加時會用直式去計算，直式就是從最右邊開始用每一位相加、進位的計算。

如果兩數的某位數相加起來超過 10，就進位 1。

若 10 -> 往左邊進位 + 1，本身變成 0。

若 11 -> 往左邊進位 + 1，本身變成 1。

// from NTUCPC Guide
const int len = 10; // 數字的最大位數（答案也不能超過這個位數）
 
void big_plus(int a[len], int b[len], int c[len]) { // c = a + b
    int carry = 0; // 上一個位數進位到這一位數
    for (int i = 0; i < len; i++) {
        int sum = a[i] + b[i] + carry; // 兩個數字的這一位數相加，再加上進位
        c[i] = sum % 10; // 總和的個位數就是答案
        carry = sum / 10; // 超出個位數的部分要進位到下一個位數
    }
}

### 減法
---

若直式在減法中上面的數字比下面小，就需要考慮借位問題。加法在程式設計上做法是將進位部分 +1 給左邊位數的，那減法則相反，將左邊的位數扣 1，等同進位 -1。

// from NTUCPC Guide
void big_minus(int a[len], int b[len], int c[len]) { // c = a - b
    int carry = 0; // 上一個位數進（借）位到這一位數
    for (int i = 0; i < len; i++) {
        int sum = a[i] - b[i] + carry; // -10 <= sum <= 9
        if (sum < 0) carry = -1, sum += 10; // 變負的要借位
        else carry = 0;
        c[i] = sum; // 現在 0 <= sum <= 9
    }
}

### 乘法
---

乘法與加法的程式設計幾乎差不多，一樣向左進位。

// from NTUCPC Guide
void big_multiplies(int a[len], int b[len], int c[len]) { // c = a * b
    for (int i = 0; i < len; i++) c[i] = 0;
    for (int i = 0; i < len; i++) {
        int carry = 0;
        for (int j = 0; i + j < len; j++) {
            // 從低位做到高位就能好好處理進位
            // (a[i] * 10^i) * (b[j] * 10^j) = (a[i] * b[j]) * 10^(i+j)
            int sum = c[i + j] + a[i] * b[j] + carry;
            c[i + j] = sum % 10;
            carry = sum / 10;
        }
    }
}

### 除法
---

比大小函數：

// from NTUCPC Guide
int comp(int a[len], int b[len]) { // -1: a < b, 0: a = b, 1: a > b
    for (int i = len - 1; i >= 0; i--) {
        if (a[i] < b[i]) return -1;
        else if (a[i] > b[i]) return 1;
    }
    return 0;
}

除法與其他運算不同，除法是從最高位數（最左邊）開始運算，其他都是從最低位數（最右邊）。

> a / b 的最高位數，就是「b 乘上它不會超過 a」的最大的數字，而這個數字也不是很好找，對人類而言只能猜猜看，好在電腦要一個一個慢慢試沒有那麼困難。在找到最高位數後，就把 a 減去 b 乘上它，接下來再找下一個位數。

void big_divides(int a[len], int b[len], int c[len], int r[len]) { // a / b = c ... r
    int t = len - 1;
    for (; t >= 0 && b[t] == 0; t--); // 找到 b 的最高非 0 位數
    int tmp[len];
    for (int i = 0; i < len; i++) r[i] = a[i], c[i] = 0;
    for (int i = len - t - 1; i >= 0; i--) { 
        // 從最大的位數開始找，要確保 b * 10^i 位數不會超過 len
        int d = 0;
        for (int j = 0; j < len; j++) tmp[j] = 0;
        for (int j = 0; j <= t; j++) tmp[i + j] = b[j]; // tmp = b * 10^i
        while (comp(r, tmp) >= 0) { // r >= tmp
            big_minus(r, tmp, r); // r = tmp - r
            d++;
        }
        c[i] = d;
    }
}

習題練習
---

1. https://zerojudge.tw/ShowProblem?problemid=a021

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

// 移除前導零（因為有些字串運算完在前面會出現 0, 如: 0001112）
string removeLeadingZeros(string s) {
    int i = 0;
    while(i < s.size() - 1 && s[i] == '0') {
        i++;
    }
    return s.substr(i);
}

// 大數加法
string addBig(const string &a, const string &b) {
    int i = a.size()-1, j = b.size()-1;
    int carry = 0;
    string result = "";
    while(i >= 0 || j >= 0 || carry) {
        int x = (i >= 0 ? a[i]-'0' : 0); // 因為 x 資料型態是 int, 所以必須寫 a[i]-'0'
        int y = (j >= 0 ? b[j]-'0' : 0);
        int sum = x + y + carry;
        carry = sum / 10;
        result.push_back(sum % 10 + '0'); // 最後 push_back 再轉回去 ASCII 碼
        i--; j--;
    }
    reverse(result.begin(), result.end());
    return removeLeadingZeros(result);
}

// 大數減法 (假設 a >= b)
string subBig(const string &a, const string &b) {
    int i = a.size()-1, j = b.size()-1;
    int carry = 0;
    string result = "";
    while(i >= 0) {
        int x = a[i]-'0';
        int y = (j >= 0 ? b[j]-'0' : 0);
        int sub = x - y - carry;
        if(sub < 0) {
            sub += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.push_back(sub + '0');
        i--; j--;
    }
    reverse(result.begin(), result.end());
    return removeLeadingZeros(result);
}

// 比較兩個大數字串（無前導零）
int compareBig(const string &a, const string &b) {
    if(a.size() < b.size()) return -1;
    if(a.size() > b.size()) return 1;
    if(a == b) return 0;
    return (a < b ? -1 : 1);
}

// 大數減法, 含負號
string subtractBig(const string &a, const string &b) {
    if(compareBig(a, b) >= 0)
        return subBig(a, b);
    else
        return "-" + subBig(b, a);
}

// 大數乘法
string mulBig(const string &a, const string &b) {
    int n = a.size(), m = b.size();
    vector<int> result(n + m, 0);
    for(int i = n - 1; i >= 0; i--){
        for(int j = m - 1; j >= 0; j--){
            int mul = (a[i]-'0') * (b[j]-'0');
            int sum = result[i+j+1] + mul;
            result[i+j+1] = sum % 10;
            result[i+j] += sum / 10;
        }
    }
    string resStr = "";
    for (int num : result) {
        resStr.push_back(num + '0');
    }
    return removeLeadingZeros(resStr);
}

// 大數除法 (取商數)
string divBig(const string &dividend, const string &divisor) {
    if(compareBig(dividend, divisor) < 0)
        return "0";
    string result = "";
    string current = "";
    for (int i = 0; i < dividend.size(); i++){
        current.push_back(dividend[i]);
        current = removeLeadingZeros(current);
        int count = 0;
        while(compareBig(current, divisor) >= 0) {
            current = subBig(current, divisor);
            count++;
        }
        result.push_back(count + '0');
    }
    return removeLeadingZeros(result);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string a, op, b;
    cin >> a >> op >> b;
    string ans;
    
    if(op == "+"){
        ans = addBig(a, b);
    } else if(op == "-"){
        ans = subtractBig(a, b);
    } else if(op == "*"){
        ans = mulBig(a, b);
    } else{
        ans = divBig(a, b);
    }
    cout << ans << "\n";
    return 0;
}


程式碼解釋：

因為這題牽涉到字串處理，需要把輸入的 + - * / 處理掉。

然後程式碼 23 行的 `a[i] - '0'` ，是因為 a[i] 本身是一個 char 資料型態，他們都有對應的 ASCII 值，如果直接用 a[i] 會出錯，如：`'3'` ASCII 碼為 51。

而 `'0'` 的 ASCII 碼為 48，若要求 3，則 `'3' - '0' = 51 - 48 = 3`，接下來的數字以此類推。

其他的部分大概就跟上面的大數運算範例差不多。

只是這題麻煩的是字串處理部分。

2. https://zerojudge.tw/ShowProblem?problemid=d481

矩陣乘法教學，個人推薦優質教師楊翰數學：https://www.youtube.com/watch?v=11H7HLNyg0Q&t=356s

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c, d;
    while(cin >> a >> b >> c >> d){
        // 檢查矩陣是否可乘
        if(b != c){
            cout << "Error" << "\n";
            continue; // 直接換下一組測資, 不讀取矩陣資料
        }
        
        // 讀取第一個矩陣 (a 列, b 行)
        vector<vector<long long>> mat1(a, vector<long long>(b));
        for (int i = 0; i < a; i++){
            for (int j = 0; j < b; j++){
                cin >> mat1[i][j];
            }
        }
        
        // 讀取第二個矩陣 (c 列, d 行)
        vector<vector<long long>> mat2(c, vector<long long>(d));
        for (int i = 0; i < c; i++){
            for (int j = 0; j < d; j++){
                cin >> mat2[i][j];
            }
        }
        
        // 計算矩陣乘法，結果矩陣大小為 a * d
        vector<vector<long long>> result(a, vector<long long>(d, 0));
        for (int i = 0; i < a; i++){
            for (int j = 0; j < d; j++){
                for (int k = 0; k < b; k++){
                    result[i][j] += mat1[i][k] * mat2[k][j];
                }
            }
        }
        
        for (int i = 0; i < a; i++){
            for (int j = 0; j < d; j++){
                cout << result[i][j] << (j < d - 1 ? " " : "");
            }
            cout << "\n";
        }
    }
    return 0;
}


變數解釋：

- a ： 第一個矩陣的行數（Row）
- b ： 第一個矩陣的列數（Col）
- c ： 第二個矩陣的行數（Row）
- d ： 第二個矩陣的列數（Col）

滿足矩陣乘法的條件，是 b、c 相同。如： 1x2 矩陣 跟 2x1 矩陣就可相乘，1x2 1x3 就不行。

假設矩陣 A、B 存在，則矩陣乘法為：

\begin{equation}
A_{m \times n} \cdot B_{n \times k} = C_{m \times k}
\end{equation}

\begin{equation}
c_{ij} = \sum_{r=1}^{n} a_{ir} b_{rj} , \quad \forall \; i = 1, 2, \dots, m, \quad j = 1, 2, \dots, k.
\end{equation}

以下範例舉例矩陣乘法的應用，線性變換（linear transformation）：

$$
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
\begin{bmatrix}
1 \\
2
\end{bmatrix} =
\begin{bmatrix}
a + 2b \\
c + 2d
\end{bmatrix}
$$

乘法結果的 1,1 項，為 $a \cdot 1 + b \cdot 2 = a + 2b$ ，2,1 項為 $c \cdot 1 + d \cdot 2 = c + 2d$ 。

那既然知道矩陣乘法的規則就可以開始寫程式了，如同上面所寫的 `result[i][j] += mat1[i][k] * mat2[k][j];`。

3. https://zerojudge.tw/ShowProblem?problemid=b893

這題順便還考你跳脫字元，真棒。

（勘根定理教學）然後再次推薦：https://www.youtube.com/watch?v=ZvjkCYVAHSs

假設實係數 $f(x) = 0$ ，則所謂勘根定理就是當 $f(a) \cdot f(b) < 0$ ，至少會有一個實根。

#include <bits/stdc++.h>

using namespace std;

// 計算多項式函數值（秦九韶算法）
double poly(const vector<int>& coeff, double x) {
    double result = 0;
    for (int i = 0; i < 6; i++) {
        result = result * x + coeff[i];
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<int> coeff(6);
    
    while (cin >> coeff[0] >> coeff[1] >> coeff[2] >> coeff[3] >> coeff[4] >> coeff[5]) {
        
        bool allZero = true; // 檢查係數是否全都 0
        for (int i = 0; i < 6; i++) {
            if (coeff[i] != 0) {
                allZero = false;
                break;
            }
        }
        if (allZero) { // 全都 0 代表無限多組根
            cout << "Too many... = =\"" << "\n";
            continue;
        }

        bool isConstant = true; // 檢查是否為常數函數
        for (int i = 0; i < 5; i++) {
            if (coeff[i] != 0) {
                isConstant = false;
                break;
            }
        }
        if (isConstant) { // 無根
            cout << "N0THING! >\\\\\\<" << "\n";
            continue;
        }

        vector<pair<int, int>> roots; // pair 關聯式容器
        bool foundRoot = false;
        
        // 因為題目限制區間 [-40, 40] 可直接暴力破解
        for (int i = -40; i <= 40; i++) {
            double val1 = poly(coeff, i);
            double val2 = poly(coeff, i + 1);

            if (fabs(val1) < 1e-9) { // 避免浮點數誤差
                roots.push_back({i, i});
                foundRoot = true;
            }

            if (val1 * val2 < 0) {
                roots.push_back({i, i + 1});
                foundRoot = true;
            }
        }

        if (!foundRoot) {
            cout << "N0THING! >\\\\\\<" << "\n";
        } else {
            for (auto &p : roots) {
                cout << p.first << " " << p.second << "\n";
            }
        }
    }
    return 0;
}


有關多項式函數值在程式設計上的計算，可見：https://ohiyooo2.pixnet.net/blog/post/403086710

C++ 解法（秦九韶算法）：https://github.com/Rocketng/Algorithm/blob/master/%E7%A7%A6%E4%B9%9D%E9%9F%B6%E7%AE%97%E6%B3%95.cpp

這邊用到了 pair 關聯式容器，因為勘根定理要求哪兩個連續整數之間有實根，所以用 pair 來表示會更加明瞭。

pair 使用 `pair.fisrt`、`pair.second` 來存取前面跟後面的資料。

然後不知道為啥 long long 會 80%，試好久改成 double 就 AC 了。