2018/7/14：普通的紀中一天

兒子兄弟表示法

將一顆多叉樹轉換為二叉樹的方法，左子節點連原樹的第一個兒子，右子節點連原樹的右邊的兄弟

適用范圍：樹形dp

數位dp常見方法

狀態壓縮

分類討論

記憶法（記憶化搜索）

手推exgcd

$$ax+by=gcd(a,b)$$
$$b{x}^{\prime }+(a\%b)y^{\prime }=gcd(b,a\%b)$$
展開$(a\%b)$
$$b{x}^{\prime }+(a??a/b?b)y^{\prime }=gcd(b,a\%b)$$
拆開括號
$$b{x}^{\prime }+a{y}^{\prime }??a/b?b{y}^{\prime }=gcd(b,a\%b)$$
將$a$和$b$取出
$$a{y}^{\prime }+b(x^{\prime }??a/b?y^{\prime })=gcd(b,a\%b)$$
$$\because gcd(a,b)=gcd(b,a\%b)$$
$$\therefore a{y}^{\prime }+b(x^{\prime }??a/b?y^{\prime })=ax+by$$
將兩邊的$a$和$b$取出
$$y^{\prime }+(x^{\prime }??a/b?y^{\prime })=x+y$$
然后由于兩邊是等價的
$$\therefore \{\begin{array}{c}x=y^{\prime }\\ y=(x^{\prime }??a/b?y^{\prime })\end{array}$$

---

2018/7/16：腐敗普通的紀中一天

gcd證明

$$我們設d=gcd(a,b)$$
$$\because d\mid a,d\mid b$$
$$\therefore d\mid a\%b$$
$$設gcd(b,a\%b)=d^{\prime }$$
$$\because d^{\prime }\mid b,d^{\prime }\mid a\%b$$
$$\therefore d^{\prime }\mid a$$
$$gcd(a,b)=gcd(b,a\%b)$$

---

2018/7/17：頹廢普通的紀中一天

時間復雜的與數據范圍

$$n?15：O(2^n)$$
$$n?70：O(n^4)$$
$$n?500：O(n^3)$$
$$n?5000：O(n^2)$$
$$n?10^4：O(n\sqrt{n})$$
$$n?10^5：O(n(logn{)}^2)$$
$$n?5?10^5：O(nlogn)$$
$$n?10^6：O(nloglogn)$$
$$n?5?10^6：O(n)$$
$$n?2147483647：O(\sqrt{n})$$
$$n?max\_longlong：O(logn)$$

---

2018/7/18：罕見正常的紀中一天

gcd的和之一

$$\sum _{i=1}^{n}gcd(n,i)$$
$$=$$
$$\sum _{d|n}\phi (n/d)\times d$$
證明與例題：https://blog.csdn.net/mr_wuyongcong/article/details/81104903

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的学习手记(2018/7/14~2018/7/18)——快乐纪中的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。