演算法筆記 - HackMD

# 演算法筆記 ## **目錄** ### 1.[STL](https://hackmd.io/L3i-dTqRTq-o0vZzCxd1XQ?both#STL) ### 2.圖論 ### 3.Sparse table ### 4.字串相關 ### 5.指標 ## 題單參考 [yui huang 的演算法筆記](https://yuihuang.com/oj-level-4/) [資讀題單](https://docs.google.com/spreadsheets/d/1pETbGRvHBhybv--MRj4N_khKetZDGWcsiRs70WNi_0A/edit#gid=589172402) ## **STL** ### (1)STACK * 從最頂端存取、刪除、新增資料 * 後進先出 #### 程式碼 ```cpp= stack <int> stk; stk.top(); //回傳stack頂端的值 stk.pop(); //刪除stack頂端的資料 stk.push(); // 將新值加入stack stk.size(); // 輸出stack的大小 ``` ### 補充：前序/中序/後序運算法 **前序** +35 **中序** 3+5 **後序** 35+ 那要如何轉換呢? **例題：後序運算法** 我們平常使用的是中序運算法，但是對電腦而言，使用後序運算法是較為方便的如果要用程式來進行中序轉後序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用迴圈，取出中序式的字元，遇運算元直接輸出；堆疊運算子與左括號；堆疊中運算子優先順序大於讀入的運算子優先順序的話，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇右括號輸出堆疊中的運算子至左括號。 ### (2)QUEUE * 先進先出 * 從最前端存取、刪除資料，從最後端新增資料 ``` cpp= queue <int> q; q.front(); //回傳 queue 最前端的值 q.pop(); //刪除 queue 最前端的資料 q.push(); //將一個新的值加入 queue 的最後端 q.size(); //回傳 queue 的大小 ``` ### (1) + (2) = deque! (雙向佇列) 對了，deque可以用insert ```cpp= #include <deque> deque <int> dq; dq.empty(); //測試 deque 是否為空。(回傳布林值) dq.size(); //查詢目前 deque 中有幾個元素。 dq.push_front();//在 deque 的前端加入一個元素。 dq.push_back(); //在 deque 的後端加入一個元素。 dq.pop_front(); //移除目前 deque 中最前端元素。 dq.pop_back(); //移除目前 deque 中最後端元素。 dq.front(); //取得目前 deque 中最前端元素。 dq.back(); //取得目前 deque 中最後端元素。 dq.insert(iterator, n, val); //插入位置/次數/值 ``` ### (3)Heap (priority_queue) * 存取、刪除 heap 最頂端的資料 (為預設的極值) * 維持極值 :::success 預設為由大至小排列，但可以再進行更改 ```cpp= priority_queue <int> pq; //由大至小 priority_queue <T, vector<T>, greater<T> > pq; //由小至大 priority_queue<T, vector<T>, cmp> pq; //自行定義 cmp 排序 ``` ::: ```cpp= pq.push(); //輸入 pq.top(); //存取最大權重值 pq.pop(); //刪除最大權重值 pq.size(); //回傳 pioraity_queue 的大小 ``` ### (4)Set * 用於插入/刪除/選取資料 * 會自動進行排序/不會選到重覆的 ```cpp= set <int> s; s.insert(); //新增 s.erase(); //刪除 s.find(); //查詢 (與iterator有關) s.count(); //查詢是否存在於集合中 s.lower_bound(val); //找出大於或等於val的最小值的位置 for (auto it = s.begin(); it != s.end(); it++) // set的遍歷 cout << *it << endl; ``` ### 補充：lower_bound and upper_bound (二分搜) 排序過的vector也可以用! ```cpp= auto it = lower_bound(v.begin(), v.end(), val); //用二分搜找出 "大於或等於" x的最小值的 "位置" auto it = upper_bound(v.begin(), v.end(), val); //用二分搜找出 "大於" x的最小值的 "位置" ``` 還不太熟練，來幾道習題吧! [APCS-圓環出口](https://zerojudge.tw/ShowProblem?problemid=f581) [APCS-牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084) [APCS-飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) [APCS-雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401) [紀念品分組](https://zerojudge.tw/ShowProblem?problemid=b159) ### (5)Map * 使用**關鍵字Key**去索引該**關鍵字的值value** * 為一對一的功能 * 可以修改value, 不能修改Key * 包含插入、修改、刪除、尋找 ```cpp= map <string, int> mp; //宣告一個 key為string, value為int 的map //插入的方法 mp[key] = value; //也可進行更改 mp.insert(pair<string, int>(Hi, 1) ); //查詢 mp.find(); //返回資料所在位置，若無則返回與end()函數相同 mp.count(); mp.erase(); //刪除 mp.clear(); //清空 ``` ### (6)Vector * 可改變容量的陣列 ```cpp= vector <int> adj; adj.push_back(); //新增尾部元素 adj.pop_back(); //刪除尾部元素 ``` ### (7)Pair * 包含兩個數值前面的稱為first, 後面的稱為second * 兩個數值可以為不同種類的數據類型 ```c++= #include <utility> pair <T1, T2> p1 // 宣告 make_pair (v1, v2) //直接使用v1 / v2來創建這個pair //pair的操作 p1.first = 1; p1.second = 2; ``` ### (8)struct 常常在排序時用到! ```c++= struct A // 結構名稱 { 結構變數; int age; int weight; bool female; //之類的 }; //這裡要有分號，別忘記了! struct A a; a.age = 16; //以此改變 ``` ### [補充：指標(還是搞不太懂= =)](https://hackmd.io/L3i-dTqRTq-o0vZzCxd1XQ?view#%E6%8C%87%E6%A8%99) ### (9) Linked list 可支援插入以及刪除某個元素，但能夠存取的節點只有開頭 ```cpp= struct Node { int val; Node *_next ; Node *_before ; Node() { _next = NULL; _before = NULL; } }; ``` ### (10) bitset ```cpp= bitset<N> b(a); // 宣告一個大小為N的bitset, 後面的a是初始化 b.count() //回傳有幾個位元是1 b.set() //將所有位元設為1 b.reset() //將所右位元設為0 ``` ## 二分搜 1. 左閉右閉 ```cpp= int binary_search(int l, int r) { while(l < r) { int m = (l+r)/2; if ( f(m) == 1 ) r = m; else l = m+1; } return l; } ``` ## 二元樹例子： [洛谷 P5076](https://www.luogu.com.cn/problem/P5076) 模板，其實跟線段樹有點像? 但傳上去只有86分，可能有bug! ```cpp= 初始建構 struct Node { int val, cnt=1, siz=1; struct Node *l=NULL; struct Node *r=NULL; }; void add(Node *now, int x) { now -> siz++; if (x < now -> val) { if (now -> l != NULL) add(now -> l, x); else { Node *son = new Node; son -> val = x; now -> l = son; } } else if (x > now -> val) { if (now -> r != NULL) add(now -> r, x); else { Node *son = new Node; son -> val = x; now -> r = son; } } else now -> cnt++; } //查詢x的排名 int query_x( Node *now, int x) { if (now == NULL) return 0; if (now -> val == x) { if (now -> l != NULL) return now -> l -> siz; return 0; } if (now -> val > x) return query_x( now -> l, x); else { if (now -> l != NULL) return now -> l -> siz + now -> cnt + query_x( now-> r, x); else return now -> cnt + query_x(now -> r, x); } } //查詢排名第x int query_num(Node *now, int rank) { if (now == NULL) return 2147483647; int lsiz; if (now -> l == NULL) lsiz = 0; else lsiz = now -> l -> siz; if (lsiz >= rank) return query_num( now->l, rank); if (lsiz + now -> cnt >= rank) return now -> val; else return query_num( now -> r, rank - lsiz - now->cnt); } //求x前面的數 (小於x且最大的數) int query_front( Node *now, int x, int ans) //找較小值 { if (now->val >= x) //比目前大就找左子樹 { if (now -> l != NULL) //有更小的就往左找 return query_front(now -> l, x, ans); else return ans; // 沒更小的了 } else { if (now -> r == NULL) //看有沒有比目前更大的，沒有輸出目前 return now -> val; else { //有就往右子樹找，先把目前可能答案紀錄 return query_front(now -> r, x, max(ans, now -> val)); } } } //求x後面的數 (大於x且最小的數) int query_next(Node *now, int x, int ans) { if (now -> val <= x) { if ( now -> r != NULL) return query_next(now -> r, x, ans); else return ans; } else { if (now -> l == NULL) return now -> val; else return query_next(now-> l, x, min(ans, now-> val)); } } ``` ## 圖論 ### 圖的儲存方式可分為**鄰接矩陣**與**鄰接陣列** * **鄰接矩陣** 在鄰接矩陣中，建立一個二維陣列A 若(u, v)之間有連通，則使A[u][v] = 1, 否則A[u][v] = 0 在無向圖中記得A[v][u]也要設定 ```c++= bool A[M][M] = 0; int u, v; cin >> u >> v; A[u][v] = 1; A[v][u] = 1; ``` * **鄰接陣列** 對於每一個點儲存一個vector, 記錄他連到的所有點 ```cpp= vector <int> adj[M]; int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); ``` ### 圖的遍歷分為**BFS(廣度優先搜尋法)** 以及 **DFS(深度優先搜尋法)** * **BFS** 使用**queue**存下可以走到但尚未走過的點然後將走過的點pop, 繼續走與他相鄰的點 * <font color="red">**可以用來記錄每個點與原點的距離!** </font> 假設每一點的權重均為1 ```cpp= vector <int> adj[M]; bool vis [M] = {0}; //紀錄是否走過 int d[M] = {-1}; //紀錄距離 queue <int> que; d[1] = 0; que.push(1); while (que.size()) { int now = que.front(); que.pop(); vis[now] = 1; for (int v:adj[now]) //對於adj[now]中的每一個點都跑一遍 { if (!vis[v]) { que.push(v); // 還沒跑過就加入que d[v] = d[now] + 1; vis[v] = 1 //並紀錄已經跑過 } } } ``` * **DFS** 走目前能走的位置，一樣記錄每個點是否走過 ```cpp= vector <int>adj[M]; bool vis[M] = {0}; DFS(1); void DFS(int n) { vis[n] = 1; for (int v:adj[n]) { if (!vis[v]) DFS(v); } } ``` ### 拓撲排序當事情有**先後順序**的時候，輸出做事情的順序思路：能做的就先做完! 將事情的先後順序看成**有向圖**，當做過該事件後刪除此點 ```cpp= vector <int> adj[M]; int deg[M] = {0}; //紀錄每個點從哪裡來的! 0即為前面沒有要先做的 int main() { for (int i=0; i<m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); deg[v]++; } queue <int> que; for (int i=1; i<=n; i++) if (deg[i]==0) //若事情前面沒有要先做的事就先跑 que.push(i); while (que.size()) { int now = que.front(); que.pop(); for (int v:adj[now]) { deg[v]--; if (deg[v] == 0) que.push(v); } } } ``` ### 樹有n個點，n-1條邊的連通圖除了**根節點**以外，每個點都有**父節點** * 在樹上進行**DFS**! 可以不用紀錄visited :::success 對於考到樹的題目，可以嘗試往整個子樹去想，不要只考慮單一節點之間的關係 ex: TOI2022 共享自行車 2020 建設人工島 ::: ```cpp= void dfs(int n, int par) { for (int v:adj[n]) if (v != par) dfs(v, n); } ``` * 記錄節點的**深度**! ```cpp= int d[M]; d[1] = 0; //此處先假設根節點為1, 要將其換成根節點喔! void dfs(int n, int par) { for (int v:adj[n]) if (v != par) { d[v] = d[n] +1; dfs(v, n); } } ``` 或者這樣也可以! ```cpp= int dep[M]; void dfs(int n, int par, int d) { dep[n] = d; for (int v:adj[n]) if (v != par) { dep[v] = dep[n] +1; dfs(v, n, d+1); } } ``` * **樹直徑** 先隨機找一點A, 找出距離其最遠的點B, 再找出距離點B最遠的點C, 點B和點C的距離即為答案! ```cpp= int dep[M]; vector <int> adj[M]; int dfs(int, int, int); int main() { for (int i=0; i<m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int u = dfs (1, 0, 0); int v = dfs(u, 0, 0); cout << dep[v]; } int dfs(int n, int par, int d) { dep[n] = d; int far = n; //紀錄距離最遠的點 for (int v:adj[n]) { if (v!= par) { int tmp = dfs(v, n, d+1); if (dep[tmp] > dep[far]) //若有更遠的就更新 far = tmp; } } return far; } ``` 相關題目：[CSES tree diameter](https://cses.fi/problemset/task/1131) #### 稍微進階的樹直徑 [CSES Tree distance](https://cses.fi/problemset/task/1132) 對每個點先找他的下面的距離然後找那個點的parent, if(d[往下走的] + 1 > d[parent]) 答案就會是d[往下走的] #### **子樹大小** #### **樹重心** ### LCA(樹的共同祖先) 有兩點a, b, 其中a**深度**較深 * 將a點走至與b點深度相同 * 若此時a = b, a即是答案 * 當深度兩者相同時，搜尋他們的祖先，記錄從何時不同 * 何時不同的上一個祖先就是答案 ```cpp= vector <int> adj[M]; int anc[18][M]; //記錄他們的祖先前面紀錄為第幾層祖先 int dfs (int n, int par, int d) { anc[0][n] = par; dep[n] = d; for (int v:adj[n]) if (v != par) dfs (v, n, d+1); } int lca(int a, int b) { if (dep[a] < dep[b]) swap(a, b); //從深度較深的開始計算 for (int i=17; i>0; i--) { if (dep[anc[i][a]] >= dep[b] ) a = anc[i][a]; //此時a的深度必定大於或等於b, 而當小於b時就不會再更新 } if (a == b) return a; for (int i=17; i>=0; i---) { if (anc[i][b] != anc[i][a]) //紀錄何時不同 a = anc[i][a]; } return anc[0][a]; //何時不同的祖先即為答案 } int main() { for (int i=1; i<18; i++) //紀錄祖先的祖先 { for (int j=1; j<node; j++) { anc[i][j] = anc[i-1][anc[i-1][j]]; } } cout << lca(a, b); //開始lca! } ``` 相關題目：[CSES company queries 2](https://cses.fi/problemset/task/1688) ### 並查集 (DSU) 用以處理**不交集**的**合併**和**查詢**問題可以查詢兩點是否相通透過不斷尋找**源頭**進行 ```cpp= p[M] = {-1}; //先將陣列進行初始化 int find_root (int x) //找尋源頭 { if (par[x] != x) //若x的源頭不等於x代表還有源頭，繼續找 return find_root(par[x]); return x; } ``` 當想讓兩者合併時先將兩者的源頭都找出來，將其中一個源頭的源頭改為另一個源頭 ```cpp= void union(int x, int y) { int rx = find_root(x); int ry = find_root(y); par[rx] = ry; } ``` 相關題目：[畢業旅行](https://zerojudge.tw/ShowProblem?problemid=d831) [我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445) ### 最短路 #### (1) Dijkstra演算法適用於**沒有負邊**的情況下想成帶有權重的BFS, 將權重和接收點用pair表示! 1. 維護一個priority_queue , 裡面存放該點的最小距離以及該點 (dis, now) 2. 取出**距離最小**的該點，若該點未被處理過，則dis即為此點的最小距離 (直接到步驟3) 3. 對now的相鄰點進行鬆弛(此時你要確定now已經不能再被鬆弛) ```cpp= priority_queue<pii, vector<pii>, greater<pii>> pq; dis[1] = 0; pq.push({0, 1}); while(pq.size()) { ll d = pq.top().f; int now = pq.top().s; pq.pop(); if (d != dis[now]) continue; // 如果不等於代表這一點已經被鬆弛過了 for (pii p: adj[now]) { int v = p.f, w = p.s; if (dis[v] > d+w) { dis[v] = d+w; pq.push({dis[v], v}); } } } ``` #### (2) Bellman-Ford演算法與先前的Dijkstra略有不同，可以運用在**有負邊**的情況，也可以檢查是否有<font color="#f00">負環</font>! 複雜度為 O($nm$) 這一點要注意!已經因為這樣好幾次TLE了= = ```cpp= const ll inf = 1LL << 60; queue<ll> q; q.push(1); while(q.size()) { int now = q.top(); q.pop(); for (pll p: adj[now]) { ll v= p.f, w = p.s; if (dis[v] > dis[i]+w) { dis[v] = dis[i]+w; q.push(v); } } } ``` ### 二分圖 1. 用DSU做當有n個點時開2*n個區域，若點a與點a+n在一起就表示不是二分圖 ### MST (最小生成樹) 1. Krusal algorithm 將邊依照權重從小到大排序，檢驗目前的點是否已經在此集合裡(用並查集檢查) 複雜度為 **O($mlogm$)** ```cpp= struct side { ll x, y, w; } sd[M]; bool cmp(sd a, sd b) { return a.w < b.w; } for (int i=0; i<m; i++) cin >> sd[i].x >> sd[i].y >> sd[i].w; sort(sd, sd+m, cmp); ll sum = 0; for (int i=0; i<m; i++) { if (find(sd[i].x) == sd[i].y) continue; Union(sd[i].x, sd[i].y); sum+=sd[i].w; } cout << sum << endl; ``` 2. Prim's algorithm 隨便選一個點當開頭，找**目前與已連接的點所連接的最小邊**，做法類似dijkstra (下面程式碼尚未完成) 複雜度為 **O($n^2$)** 或 **O($m logm$)** ```cpp= vector<pii> adj[M]; for (int i=0; i<m; i++) { int a, b, w; cin >> a >> b >> w; adj[a].push_back(w, b); adj[b].push_back(w, a); } for (int i=0; i<n; i++) sort(adj[i].begin(), adj[i].end); int sum = 0; priority_queue<pii>pq; ``` ## 區間問題整理在這個[簡報](https://slides.com/yujuan/desk)裡了! 題目敘述:給你一個長度為N的數列，接下來有q筆詢問詢問的類型有: (1)將[l, r]之間的數字全部加上x (2)輸出[l, r]這個區間的最大值 ### 前綴和當問 [l, r]之間的和時先記錄從第 1 項到第 i 項的和那第 l 項到第 r 項的和就是 (1-r) - (1-l) ### 差分序列當我們有 [ a1, a2, a3, a4.. an]的序列時紀錄 ( a2 - a1 ) , ( a3 - a2 ) , ### Sparse table 有概念了，但不太清楚，先放個別人的[參考程式碼](https://hackmd.io/@alanlai/HkZ5NqyDt) #### 概念：將其先一開始每個均為一塊，然後將其不停**合併** (不同塊之間可重疊!) ![](https://i.imgur.com/mVvIH03.jpg) 以$s[i][j]$表示從 $i$ 開始，長度為$2^j$的範圍 (也就是終點為 $i + 2^j -1$!) 例如$s[i][0]$表示從$i$開始，長度為$2^0 = 1$的範圍，也就是只有$i$自己! $s[i][1] 會等於 s[i][0] + s[$ 所以當我們要求長度為$n$的最大值時，需要 **$j = [\log_2n$]** 然後用DP更新 ```cpp= int N; int s[1005][1005]; int log2[1005]; //紀錄那個數字log2是多少 int num[1005]; for (int i=0; i<N; i++) { cin >> num[i]; s[i][0] = num[i]; } //2的j次方為 1 << j 或 pow(2,j) //建n以內log2的表 log2[1] = 0; for (int i=2; i<N; i++) log2[i] = log[i/2] +1; //做無條件進位 for (int j=1; j<log2[N]; j++) { for (int i=0; i+pow(2,j) - 1<N; i++) s[i][j] = max(s[i][j-1], s[i+pow(2,j)][j-1] ) ; } ``` ## 字串 ### 處理字串的方式 ### Stringstream的用法可以用來將字串進行分割，或將其與Int進行轉換，首先引入標頭 ```cpp= #include <sstream> ``` **(1)將int轉換成stream** stringsteam提供 **<<** 和 **>>** 來進行**讀取**以及**輸入** ```cpp= #include <sstream> int main() { stringstream s1; int number 1234; string output; // 要進行轉換的string容器 s1 << number; //將number的值輸入至s1中 s1 >> output; cout << output; //如此一來得到的就會是1234啦! } ``` 相反的，也可以將stream轉換成int! **(2)字串分割** 先進先出，會以空白鍵作為分界 ```cpp= stringstream ss; string a = " I am a girl"; ss << a; string output; ss >> output ; cout << output ; // 這樣就會得到I! ss >> output; cout << output; //此時就會得到am囉 ``` ### 小數點後幾位 https://it-easy.tw/cout-float/ 運用 setprecision ```cpp= cout << fixed << setprecision (2) << 1.235 << endl; //這樣輸出結果就會是1.23! ``` ### 對齊我的輸出~ 運用setw(); ```cpp= cout << setw(4) << 123456; //這樣輸出結果就是1234! ``` ### Substr 顧名思義就是子字串用法為 string (開頭位置，後面幾個), 若無結束位置就到底 ```cpp= string a = "abcdefg"; cout << a.substr(2, 5); // cdefg ``` ### replace 取代字串 ```cpp= s1.replace(n1, k, string2); //將s1中從n1開始後k個用s2取代 ``` ### insert [參考資料](https://blog.csdn.net/yhc166188/article/details/83545621) ### to_string(待查) ### next_permutation ### getline ```cpp= getline(cin, str, '結束字元'): example: str = 123456; cout << getline(cin, str, '5'); //answer = 12345 ``` ## 台大資管會用到的函式(字串 ### cin.getline(跟樓上的很像) only for char string! (char 資料型態的string) ```cpp= cin.getline(str, len); ``` ### 大小寫 ```cpp= toupper(char) //變大寫 tolower(char) //變小寫 isupper(char) //判斷是否是大寫 islower(char) //判斷是否是小寫 ``` ### strchr ```cpp= ``` ### strstr ### ispunct ## DP 排列 ```cpp= ``` 組合 n 為可能幣值 , x為總和 ```cpp= for (int i=1; i<=n; i++) for (int j=0; j<=x; j++) if (i-coin[j] >= 0) { combination[j] = combination[j-coin[i]] + combination[j]; } ``` 範例：現有 (1, 3, 5)共3種幣值，要湊5元，可能的組合為? 當只有1元組合時，有 1 種當有1、3元組合時，可以在 1有兩個的時候出來一個分支，所以有1+1 = 2種組合與排列回圈內外順序相反，畫成不一樣的樹 ### backstracking (窮舉) (回溯) 例題：[zerojudge229 括號匹配問題](https://zerojudge.tw/ShowProblem?problemid=a229) ```cpp= vector<vector<int>> result; void backtrack_helper (路徑, 下一步選擇清單) { if ( 終止條件 ) result.add (路徑); return; for 下一步 in 選擇清單做選擇 backtrack_helper (路徑, 下一步選擇清單) 撤銷選擇 } ``` ## 指標指標相關 | | * | & | | -------- | -------- | -------- | | **宣告時** | 宣告指標 | 宣告參考變數(幾乎跟原本一模一樣的變數) |**非宣告時** | 取值符號 (取得指標變數指向的值) | 取址符號 (變數的記憶體位置) | **對參考變數的改變也會改到原本的變數喔！** ```cpp= * //為宣告指標用 e.g. int *ptr //這代表這是一個指向int的指標 & //為取址運算子 e.g. int *ptr = &a //a必須要是int struct p a; a.b ->表示指向的結構變數的內容 (*times1).p //與下者相等 times1->p -> ``` struct 裡的function (函式直接寫在struct內部) 範例： ```cpp= struct p { double h; double w; double BMI() { return this-> w/ (this->h * this->h); //this為物件本身的指標但this也可以省略 } }; ``` ## 快速冪計算$a^n$ 將n改為二進位，如果此時是1，就相乘 ```cpp= int power(int a, int n) { int ans = 1; for (; n; n/=2) { if (n&1) ans = ans*a; a = a*a; } } ``` ## Greedy ### 排程問題只有一個->按照**結束時間**從早開始排 pf 參考2023資訊之芽手寫作業4 多個->結束時間+製作時間從小到大排序 ## 數學 ### 找質數歐拉篩 ```cpp= bool isPrime[M]; vector<int> prime; fill(isPrime, isPrime+M+1, 1); for (int i=2; i<M; i++) { if (isPrime[i]) prime.push_back(i); for (int j: prime) { if (j*i > M) break; isPrime[i*j] = 0; if (i % j == 0) break; // 直到此質數是自己的因數，當跑到i/j時就會跑過了 } } ``` ### 找同餘? 模擬元 ## 酷酷待查的東東 ### enum ### next_premutation

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.