owned this note
owned this note
Published
Linked with GitHub
[TOC]
# 第一章
## long long
- `long long ll = 123456789LL;`
## IO
- 用來加快IO
```c++
ios::sync_with_stdio(0);
cin.tie(0); //解除cin、cout綁定
```
# 第二章
## 求Maximum subarray sum
- p.33
- $O(n)$
```c++=
int arr[]= { -1, 2, 4, ..., -5, ...};
int sum = 0;
int best = 0;
for(int i=0; i < k; i++){
//取 -1 [2 4 ...] -5
//這樣就不會取到 [-1 2 4 ...]，可以避免加到-1
sum = max(arr[i], sum + arr[i]);
best = max(best, sum);
}
```
# 第三章 Sorting
## Binary Search
- p.32
- $O(log(n))$
- b為移動長度，每次移動$\frac{n}{2^i}$，i=1，直到b == 1
```c++=
int k = 0;
for(int b = n / 2; b >= 1;b /= 2){
while(k + b < n && arr[k + b] <= x)
k += b; //向右移動
}
if(arr[k] == x)
cout<<"Find\n";
```
## Maximum value
- $f(x) < f(x+1)$ when $x<k$
- Increasing
- $f(x) > f(x+1)$ when $x\ge k$
- Decreasing
- 此時k為該區域最大值
- :arrow_right: $f(x+1)$為最大值 :arrow_right: $x$ 需加一
```c++=
int x = -1;
for(int b = n; b >= 1; b /= 2){
while(x + b + 1 < n && a[x + b] < a[x + b + 1])
x += b;
}
cout<<a[x + 1]<<endl;
```
# 第五章 -- Complete Search
## 產生所有Subset
- 兩種方法
- recursive
- bit operation
### recursive
- 左邊 :arrow_right: 不會將k納入
- 右邊 :arrow_right: 將k納入
- k從0開始，n為3
- 印出0~2的subset
:::spoiler Code
```c++=
vector<int> nums;
void recursive(int k, int n) {
if (k == n) { //當達到目的 -> 印出來
for (auto x : nums) cout << x << " ";
cout << endl;
return;
}
recursive(k + 1, n); //左邊 -> 不會將k納入
nums.push_back(k); //納入
recursive(k + 1, n); //右邊 -> 會將k納入
nums.pop_back(); //回復狀態
}
```
:::
### bit operation
- 遍歷$0$~$2^n-1$
- 使用`1<<n`
- Example ~這邊順序是由右到左~
- 5 -> `101` -> `{0,2}`
- 3 -> `011` -> `{0,1}`
:::spoiler Code
```c++=
int n = 3;
for (int i = 0; i < (1 << n); i++) { //產生0~2^n-1
for (int j = 0; j < n; j++) { //一個一個bit檢查
if (i&(1 << j)) cout << j << ' ';
} //檢查是否第j位是否有值
cout << endl;
}
```
:::
## permutation
- Recurisve
- function
### Recurisve
:::spoiler Code
```c++=
int n = 3;
vector<int> num;
vector<bool> che(n);
void recur() {
if (num.size() == n) { //陣列滿了 -> 印
for (auto x : num) cout << x << " ";
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
if (che[i]) continue; //如果有在陣列 -> 跳過
//把他加入陣列
che[i] = true;
num.push_back(i);
//recursive
recur();
//跑回來時，已經不需要 -> pop掉
che[i] = false;
num.pop_back();
}
}
```
:::
### next_permutation
- `<algorithm>`
- return value
- 好了 :arrow_right: false
- `next_permutation(v.begin(), v.end())`
- 補充
- `prev_permutation(v.begin(), v.end())`
```c++=
do{
//do something
} while(next_permutation(v.begin(), v.end()));
```
- `next_permutation`原理
- [參考](https://www.cnblogs.com/eudiwffe/p/6260699.html)
:::spoiler C語言pointer版本(方便理解)
```c++=
// STL next permutation base idea
int next_permutation(int *begin, int *end)
{
int *i=begin, *j, *k;
// 沒有東西 or 只有一個 不用做
if (i==end || ++i==end) return 0; // 0 or 1 element, no next permutation
for (i=end-1; i!=begin;) {
j = i--; // find last increasing pair (i,j)
if (!(*i < *j)) continue;
//找到離end最近 && 大於等於i 的元素
for (k=end; !(*i < *(--k)););
iter_swap(i,k); //交換
// now the range [j,end) is in descending order
reverse(j,end);
return 1;
}
// current is in descending order
reverse(begin,end);
return 0;
}
```
:::
## Queen
- 規則
- 不能同一個column、斜對角
- 需要三個vector紀錄
- column、左斜對角、右斜對角
:::spoiler Code
```c++=
#define N 4
int cou = 0;
vector<bool> col(N);
vector<bool> l_r(N * 2 - 1);
vector<bool> r_l(N * 2 - 1);
void queen(int y, int n) {
if (y == n) { //已達方法
cou++;
return;
}
for (int i = 0; i < n; i++) {
if (col[i] | l_r[(n - 1) - y + i] | r_l[y + i])
continue; //若該位置已有人
col[i] = l_r[(n - 1) - y + i] = r_l[y + i] = 1; //放置
queen(y + 1, n);
col[i] = l_r[(n - 1) - y + i] = r_l[y + i] = 0; //拿起來
}
}
```
:::
## Meet in the middle
- [Reference Video](https://youtu.be/naz_9njI0I0?si=1XWdPQKKjs_NCndI)
- `[2,4,5,9]` 目標 = 15
- 先拆分成`[2,4]`、`[5,9]`
- 擴展成`a = [0,2,4,6]`、`b = [0,5,9,14]`
- 須將<font color=red>b做sort</font>，方便之後找可以用<font color=red>Binary Search</font>
- 算 $目標 - a_i = x$，算$max(x_i \subset b \wedge x_i \le x)$，再將$ans = max(a_i + x_i)$
- 先選`0`，15 - 0 = 15，選擇$\{x_i|x_i\subset b \wedge x_i \le 15\} = 14$，$14 + 0 = 15$
- 選`2`，15 - 2 = 13，選擇$\{x_i|x_i\subset b \wedge x_i \le 13\} = 9$，$9 + 2 = 11$
- 選`4`，15 - 4 = 11，選擇$\{x_i|x_i\subset b \wedge x_i \le 11\} = 9$，$9 + 4 = 13$
- 選`6`，15 - 6 = 9，選擇$\{x_i|x_i\subset b \wedge x_i \le 9\} = 9$，$9 + 6 = 15$
- $\because \ 15 == 15$，所以有找到
- $O(Nlog(2^{N/2}))$
- Generate + Sort + Search
- $2^{n/2}$ + $2^{n/2}$ + $\cfrac{N}{2}2^{n/2}$ + $\cfrac{N}{2}2^{n/2}$
- Search : $\frac{N}{2}$(a有$\frac{N}{2}個$) $\times$ $2^{N/2}$(BS)
- [Leetcode](https://leetcode.com/problems/closest-subsequence-sum) :no_entry:
# 第六章 -- Greedy
## Scheduling
- [LeetCode](https://leetcode.com/problems/maximum-length-of-pair-chain/)
- 先將<font color=red>end time</font>做sort，由小到大
- 選擇`arr[0]`
- 選擇時間不會卡到 && end time最近~不用太考慮這點~，重複此動作
## Job Sequencing Problem
- [參考](https://www.geeksforgeeks.org/job-sequencing-problem/)
- 敘述
- 有N組`{deadline,profit}`的工作，若超時了就<font color=red>獲得不到</font>profit
- 求最大利益
- 方法
- 先<font color=red>sort</font>，依照<font color=red>profit遞減</font>
- 陣列`slop`去記錄當天**是否有工作**
- 陣列`result`紀錄當天是甚麼工作
- [題目](https://www.geeksforgeeks.org/problems/job-sequencing-problem-1587115620/1)
:::spoiler Code
```c++=
/*
struct Job
{
int id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on deadline
}; */
class Solution
{
public:
static bool cmp(Job a, Job b){
return a.profit > b.profit;
}
vector<int> JobScheduling(Job arr[], int n)
{
vector<bool> slop(n); //記錄當天是否有工作
vector<int> result(n); //紀錄當天是甚麼工作
int ans_n = 0, ans_pro = 0;
sort(arr,arr+n,cmp);
for(int i=0;i<n;i++){
for(int j=min(n,arr[i].dead)-1; j>=0; j--){
if(slop[j] == false){ //那天沒工作
slop[j] = true;
result[j] = i;
break; //因為有工作了所以不用再看
}
}
}
//紀錄結果
for(int i=0;i<n;i++){
if(slop[i]){
ans_n++;
ans_pro += arr[result[i]].profit;
}
}
vector<int> ans = {ans_n,ans_pro};
return ans;
}
};
```
:::
# 第七章 -- DP
- 要訣
- sort
- Visualization
- two sequence -> use matrix
## Coin Problem
- 概念based recursive，寫法based **iterative**
- $O(nk)$
- n : 目標值(amount)
- k : coins量
- $solve(0) = 0$
- $solve(10)=solve(7)+1=solve(4)+2=solve(0)+3=3$
- 若10\$從$\{1,3,4\}$中找零錢
- 10 = 3 + 3 + 4
- [LeetCode](https://leetcode.com/problems/coin-change)
:::spoiler Code
```c++=
int amount = 17;
vector<unsigned int> value(amount + 1,INT_MAX);
vector<int> first(amount + 1);
vector<int> coins = { 1,2,5 }; //記錄錢數量
value[0] = 0; //代表0$時，找0個硬幣
for(int i = 1; i <= amount; i++){
for(auto c:coins){
//代表i$扣掉硬幣c時，相較原本i$有更佳解
if(i - c >= 0 && value[i - c] + 1 < value[i]){
value[i] = value[i - c] + 1; //更新
first[i] = c; //紀錄第一個 -> 之後再靠first[i-c]回推
}
}
}
if(value[amount] == INT_MAX) //當無法找錢時
cout<<"Can't\n";
else
cout<<value[amount]<<endl;
//若要印出組成
int tmp = amount;
while(tmp >= 0 && first[tmp]){
cout<<first[tmp]<<" ";
tmp -= first[tmp];
}
```
:::
:::spoiler 概念圖
- coins = {1,2,3}
:::
### 延伸 -- Numbers of Coin Problem
- 問題
- 有1$、3\$、4\$，請問幾種支付4$的方式?
- 4 = 1+1+1+1 = 1+3 = 3+1 = 4
- <font color=red>找出<b>所有</b>的組合，包含<b>重複</b>的組和</font>
- 與之前差別就是會將前c個的值加起來，而非取最小
:::spoiler Code
```c++=
int amount = 2;
vector<int> count(amount + 1);
vector<int> coins = { 1,3,4 };
count[0] = 1;
for (int i = 1; i <= amount; i++) { //蒐集1~amount的problem組合
for (auto c : coins) { //每種problem的前c答案
if (i - c >= 0)
count[i] += count[i - c];
}
}
if (count[amount] == 0) //找不到
cout << "Can't" << endl;
else //找到
cout << count[amount] << endl;
```
:::
---
- 問題
- 有1$、3\$、4\$，請問幾種支付4$的方式?
- 4 = 1+1+1+1 = 1+3 = 4
- <font color=red>只考慮了在<b>該金額之前</b>的硬幣組合，而<b>不會</b>重複考慮<b>已經計算過</b>的硬幣組合</font>
:::spoiler Code
```c++=
int amount = 5;
vector<int> coins = { 1,2,5 };
vector<int> count(amount + 1);
count[0] = 1;
for (auto c : coins) { //先弄coins
for (int j = 1; j <= amount; j++) { //再弄每種problem
if (j - c >= 0) {
count[j] += count[j - c];
}
}
}
cout << count[amount] << endl;
```
:::
## Longest increasing subsequence
- $O(n^2)$
- 會往前找
1. 符合順序(Increasing)
2. ~若接上有~比較大的sequence
- [LeetCode](https://leetcode.com/problems/longest-increasing-subsequence)
:::spoiler Code
```c++=
vector<int> nums = { 6,2,5,1,7,4,8,3 };
vector<int> length(nums.size(), 1);
for (int k = 0; k < nums.size(); k++) {
for (int i = 0; i < k; i++) { //往前找(0~k)找符合順序&length[i]+1
if (nums[i] < nums[k]) {
length[k] = max(length[k], length[i] + 1);
} //更新
}
}
for (int k = 0; k < nums.size(); k++)
cout << "solve(" << nums[k] << ") = length(" << k << ") = " << length[k] << endl;
```
:::
### $O(nlog(n))$ 方法 -- Patience sort
- [LeetCode -- 題解](https://www.youtube.com/watch?v=l2rCz7skAlk&ab_channel=HuaHua)
- $O(nlog(n))$
- $O(n) \times O(log(n))$
- 有n個 $\times$ BS
- [Patience Sort Code](https://www.geeksforgeeks.org/patience-sorting/)
- $O(n^2)$
- takes $O(N)$ time to locate such a pile
- 然後有N個element
- 不常用，但概念很不錯
- 先分堆，再merge
:::spoiler Pseudocode
```c
分堆(vector<int> arr)
vector<vector<int>> piple;
for(i = 0; i < arr的長度; i++)
if(piple 為空)
新建一個vector<int> tmp
加入arr[i]
piple.push_back tmp
else
flag = 1;
for(j = 0; j < piple的長度; j++)
if arr[i] < piple[j].back()
piple[j].push_back arr[i]
flag = 0;
if flag 為 true
建一個vector<int> tmp
加入arr[i]
piple.push_back tmp
merge(piple)
merge(vector<vector<int>> piple)
vector<int> ans
while True
Max = INT_MIN
Max_index = -1
for(i = 0; i < piple的長度; i++)
if Max < piple[i].back()
Max = piple[i].back()
index = i
ans.push_back(piple[Max_index])
piple[Max_index].pop_back()
if piple[Max_index] 為空
piple.erase(piple.begin() + Max_index)
if piple 為空
break
```
:::
- [Patience Sort Code2](https://reurl.cc/2zpDyO)
## Paths in a grid
- $O(n^2)$
- 會根據棋盤上的左邊和上面來決定要怎麼走
- (對於左邊)走右還是(對於上面)走下
- 缺點是棋盤要擴大
- $5\times 5$ :arrow_right: $6 \times 6$
- 多出來的
- **value設為0**
- 會比較好做
- 比較 : recursive可以避免掉
- 條件到就直接return
:::spoiler Code
```c++=
int n = 5; //棋盤大小
vector<vector<int>> graph = {
{0,0,0,0,0,0}, //這邊棋盤要擴大 5*5 -> 6*6
{0,3,7,9,2,7},
{0,9,8,3,5,5},
{0,1,7,9,8,5},
{0,3,8,6,4,10},
{0,6,3,9,7,8} };
vector<vector<int>> sum(6, vector<int>(6)); //answer
for (int y = 1; y < 6; y++) {
for (int x = 1; x < 6; x++) {
sum[y][x] = max(sum[y - 1][x], sum[y][x - 1]) + graph[y][x];
} //左->右 上->下 目前位置
}
cout << sum[n][n] << endl;
```
:::
## 0/1 Knapsack Problem
- 預先將$k$排好順序，會減少做的時間
- 有$k=\{1,3,3,5\}$，去組合權重為$Wi$
- <font color=red><b>不能使用重複的k</b></font>
- $O(nW)$
- $n=|k|$
- $W$為要算的$Wi$有多少個
- 根據已有的True，用剩下還沒使用的$k$去往外擴(概念:左->右)
- 計算順序要改成由<font color=red>後面</font>開始，才不會覆蓋左上方的格子
:::spoiler Code -- 課本範例，看是否能組成
```c++=
int w = 12;
vector<bool> nums(w + 1);
vector<int> k = { 1,3,3,5 };
nums[0] = 1;
for (int j = 0; j < k.size(); j++) {
for (int i = w; i >= 0; i--) {
//根據已有的True，去往外擴(左->右)
if (nums[i]) nums[i + k[j]] = 1;
}
}
for (int i = 0; i <= w; i++) printf("%3d", i);
cout << endl;
for (auto x : nums) cout << " " << (x ? "O" : "X");
```
:::
:::spoiler Code 範例，看組成最大值是多少
```c++=
int n = 4;
int w = 8;
vector<int> weight = { 0,1,2,5,6 };
vector<int> size = { 0,2,3,4,5 };
vector<int> c(w + 1);
vector<int> best(w + 1);
for (int i = 1; i <= n; i++) {
for (int j = w; j >= 0; j--) {
if (j - size[i] >= 0) {
c[j] = max(c[j], c[j - size[i]] + weight[i]);
best[j] = size[i];
//這個要記長度，不能記i
//因為之後要回推時，要用長度回推，不是用i去扣
}
}
}
cout << "weight " << w << " : " << c[w] << endl << "組成 : ";
int tmp_i = w;
while (tmp_i && best[tmp_i]) {
cout << best[tmp_i] << " ";
tmp_i -= best[tmp_i];
}
```
:::
## Knapsack Problem
- 拿出來，放新的進去試試看
- 比較大，放新的
- 比較小，放舊的回去
## LCS
- 用最少編輯次數，來改變字串
- "MOIVE" :arrow_right: "LOVE" 要花多少步呢?
- [LeetCode](https://leetcode.com/problems/longest-common-subsequence/)
:::spoiler Solution
:::
- $cost(a,b)=\begin{cases}
0,\ when\ \ x[a] = y[b] \\
1,\ otherwise
\end{cases}$
- $dis(a,b)\ =\ min(dis(a,b-1)+1,\ \ dis(a-1,b)+1,\ \ dis(a-1,b-1)+cost(a,b))$
- $dis(a,b-1)$
- insert a char 在a的後面
- "ABC" :arrow_left: "AB"
- $dis(a-1,b)$
- remove a char 在a後面
- "AB" :arrow_left: "ABC"
- $dis(a-1,b-1)$
- match or modifiy a的最後char
- "ABC" :arrow_left: "ABD"
:::spoiler Code
```c++=
bool cost(char a, char b) {
return !(a == b);
}
```
```c++=
string b = " MOVIE";
string a = " LOVE";
int m = a.size() - 1;
int n = b.size() - 1;
vector<vector<int>> dis(m + 1, vector<int>(n + 1));
//因為前面有空白字元，所以要填充0~m、0~n
for (int i = 1; i <= m; i++) dis[i][0] = i; //" " vs. "LOVE"
for (int i = 1; i <= n; i++) dis[0][i] = i; //"MOVIE" vs. " "
for (int i = 1; i <= m; i++) { //row
for (int j = 1; j <= n; j++) { //col
//選擇方法，insert、remove、modify(或不動)
dis[i][j] = min({ dis[i][j - 1] + 1, dis[i - 1][j] + 1,dis[i - 1][j - 1] + cost(a[i],b[j]) });
}
}
cout << " M O V I E\n"; //印
for (int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
for (auto y : dis[i])
cout << y << " ";
cout << endl;
}
```
:::
## Counting Tilings
- [題目](https://cses.fi/problemset/task/2181/)
- [Code](https://yuihuang.com/cses-2181/)
## Kadane's algorithm
- [參考](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)
- Maximum Subarray
- 版本一
- 若全為負數，也可以找最大
- 步驟
- 先加
- 找最大
- 負->歸零
- 版本二
- 若全為負數，<font color=red>不可以</font>找最大
- 只會變0
- 步驟
- max(先加,歸零) //因為加起來可能會為負
- 找最大
:::spoiler 版本一
```c++=
vector<int> nums = { -2,1,-3,4,-1,2,1,-5,4 };
int max_sum = INT_MIN;
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
max_sum = max(sum, max_sum); //取答案
sum = max(0, sum); //若為負 -> 歸零
}
cout << max_sum << endl; //answer
```
:::
:::spoiler 版本二
```c++=
int sum = 0;
int best = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
sum = max(0, sum + nums[i]);
best = max(best, sum);
}
cout << best << endl;
```
:::
# 第八章 -- Amortized Analysis
- ==分析最壞性能的每次運行的平均時間(runtime)，但不能確認實際平均情況的性能== ?????
## Two Pointer
- [參考](https://reurl.cc/E49RM0)
- 可用於vector、linked list、string
### 左右指標
- 多用於Array 或 String
- 在適當情況下，移動其中的一個或兩個指標
- 指標方向可<font color=red>同</font>方向或<font color=red>反</font>方向
### 快慢指標
- 多用於Linked-list
- 透過 slow 與 fast 兩指標，讓兩個指標保持一定的間隔規律
#### 找Linked List中心點
- slow走一步，fast走兩步
:::spoiler 範例
:::
#### 找Linked List倒數第k點
- fast先走k步
- slow、fast再用同速度走
:::spoiler 範例
:::
#### 有無cycle
- slow、fast用不同速度走
- 早晚會遇到
:::spoiler 範例
:::
## Subarray Sum
#### 課本算法
- $O(n)$
- `left`每次只走一步
- `right`從left開始走
- 每次將走過的紀錄起來
- count = left $+\cdot \cdot \cdot+$ right
- 直到 count<font color =red> 大於 </font>target_sum~且如果大於不能算進去count~
- 直到找到`target_sum`
- [LeetCode](https://hackmd.io/@LazyBear0425/LeetCode7#560-Subarray-Sum-Equals-K)
#### 補充算法
:::spoiler Code
```c++
vector<int> v = {1,3,2,5,1,1,2,100};
int x = 100;
auto l = v.begin();
auto r = v.begin();
int sum = 0;
while(l != v.end()){
if (r !=v.end() && sum < x + *r)
sum += *r, r++;
else
sum -= *l, l++;
if (sum == x)
return true;
}
return false;
```
:::
## Two Sum
- $O(nlog(n))$
- Sort + 找
- $O(nlog(n))$ + $O(n)$
- 先<font color=red>sort</font>
- `left`每次只走一步
- `right`從**最後**開始走
- 直到找到left + right <font color=red>$\le$</font> target_sum，才停下
- 直到找到`target_sum`
### Three Sum
- $O(n^2)$
- [LeetCode](https://hackmd.io/@LazyBear0425/LeetCode1#15-3Sum)
## Nearest smaller elements
- $O(n)$
- (push + pop) $\times$ n element
- $O(1) \times O(n)$
- 用**Stack**
- remove stack.top
- until top < current element
- Example
- stack : `1,3,4`, current : `2`
- remove `3,4` -> stack : `1`
- push `2` -> stack : `1,2`
- [LeetCode](https://hackmd.io/@LazyBear0425/LeetCode1#496-Next-Greater-Element-I)
## Sliding Window Minimum
- 和[Nearest Smaller Elements](https://hackmd.io/v-lY_zPNSoGRap9s2sS2Ig?both#Nearest-smaller-elements)同理
- $O(n)$
- 用**priority_queue**實作
- 要找出window內的最小值，且window size固定
- remove queue.back
- until back **<** current element <font color=gray>or</font> queue empty
- <font color=gray>or</font> out of window size
- [LeetCode](https://leetcode.com/problems/sliding-window-maximum)
- [程式碼範例](https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/)
- 用<font color=red>priority_queue</font>
- 從k開始，並把每項加入priority_queue
- 要<font color=red>記錄index</font>
- 若超出window && 非top -> 不會即時吐出去~條件到了自然退出~
```c++
while (heap.top().second <= i - k) //過時了
heap.pop();
```
- priority_queue的<font color=red>top</font>即為答案
:::spoiler function
```c++=
vector<int> maxSlidingWindow(vector<int>& arr, int k)
{
vector<int> ans;
priority_queue<pair<int, int> > heap;
//處理 0~k-1
for (int i = 0; i < k; i++)
heap.push({ arr[i], i });
ans.push_back(heap.top().first); //1st answer
//start
for (int i = k; i < arr.size(); i++) {
heap.push({ arr[i], i });
while (heap.top().second <= i - k) //篩掉超出範圍
heap.pop();
ans.push_back(heap.top().first); //輸出answer
}
return ans;
}
```
:::
- Deque
- 處理<font color=red>front</font>
- 若超出範圍
- 即時過濾
```c++
while ((!Qi.empty()) && Qi.front().second <= i - K)
Qi.pop_front();
```
- 處理<font color=red>back</font>
- pop掉尾巴
- 直到 back > current element
```c++
while ((!Qi.empty()) && arr[i] >= Qi.back().first )
Qi.pop_back();
```
- Priority_queue vs. deque
| STL | Priority_queue | deque |
|:--------------:|:----------------:|:--------:|
| 超出範圍的退出 | 時間到了自然退出 | 手動篩選 |
# 第二十一章
## 質數運算
### number of factors
- Example
- $\tau(84) = 3 \times 2 \times 2$
- 84 : 1,2,3,4,6,7,12,14,21,28,42,84，共12個
### sum of factors
- $\sigma(84) = \cfrac{2^3-1}{2-1} \cdot \cfrac{3^2-1}{3-1} \cdot \cfrac{7^2-1}{7-1} = 7 \cdot 4 \cdot 8 = 224$
- $1+2+3+4+6+7+12+14+21+28+42+84=224$
### product of factors
- $\mu(84) = 84^6$
- $\because 1\cdot84、2\cdot42、3\cdot28\ ...\ 7\cdot12$
## GCD
```c++=
int gcd(int a, int b){
if(a == 0) return b;
else return gcd(b, a%b);
}
```
### number of coprime
- 用Euler's totient function
- Example
- $\varphi(n) = \prod^{k}_{i=1} p^{a_i-1}_i(p_i-1)$
- $\varphi(12) = 2^1\cdot(2-1)\cdot3^0\cdot(3-1) = 4$
- 備註
- 若$n$為質數
- $\varphi(n) = n-1$
## LCM
- 公式
$lcm(a, b) = \cfrac{ab}{gcd(a,b)}$
## 求$x^n\%m$較快方法
- p.33
- $O(log(n))$
- 原方法 : $(x\%m)^n\%m$
- $O(n)$
```c++=
int modpow(int x,int n,int m){
if(n == 0) returm 1 % m;
long long u = modpow(x, n / 2, m);
u = (u * u) % m; //x^(n/2) * x^(n/2)
if(n % 2 == 1) u = (u * x) % m; //x^(n-1) * x
return u;
}
```
## 計算$x^{-1}\%m$
- 若m為質數
- == $x^{m-2}\%m$
# 補充
## Eulerian path and circuit
- [參考](https://www.geeksforgeeks.org/eulerian-path-and-circuit/)
- 每個Edge會遍歷過一次
- Eulerian circuit
- 所有Degree皆為偶數
- 為Eulerian path，但start和end為同一node
- Eulerian path
- 零個或兩個node的Degree為奇數，其他皆為偶數
- use DFS
## Sollin's Algorithm
- 步驟
1. 將各頂點視為獨立的一棵樹
2. 就每棵樹挑出成本最小的邊，並加入此樹
3. 刪除重複挑出的邊，只保留一份
4. 重複②~③直到只剩一棵樹，或是無邊可挑
Google Drive
Gist
Clipboard
Sign in with Wallet
