Lruihao's Note

1 欧拉函数是求小于 x 并且和 x互质 的数的个数

通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中 p1, p2……pn 为 x 的所有质因数，x 是不为 0 的整数
φ(1)=1（唯一和 1 互质的数就是 1 本身）【注意：每种质因数只一个。比如 12=223】

2 定理

1. 若 n 是素数 p 的 k 次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了 p 的倍数外，其他数都跟 n 互质
2. 欧拉函数是积性函数——若 m,n 互质，φ(mn)=φ(m)φ(n)

3 特殊性质

1. 当 n 为奇数时，φ(2n)=φ(n)
2. p 是素数，φ(p) = p - 1，φ(p) 称为 p 的欧拉值
3. 若 a 为素数，b mod a=0,φ(a*b)=φ(b)*a

题目链接

大意：
要从城市 1 到城市 N 运送货物，有 M 条道路，每条道路都有它的最大载重量，问从城市 1 到城市 N 运送最多的重量是多少。
其实题意很简单，就是找一条 1–>N 的路径，在不超过每条路径的最大载重量的情况下，使得运送的货物最多。一条路径上的最大载重量为这个路径上权值最小的边；

看到知乎，百度的页面 F12 检查后都会有一些有趣的招聘信息。于是乎我也想给我的博客加一个。
我主要用到的工具：

• console.log()
• Notepad++
• 在线图片转文字工具

题目链接 密码：l9sn
终于不爆零了，但是还是 wa 了无数次，有时候代码感觉都差不多

题目链接
思路参考 1,思路参考 2（没看懂）

1 题目链接：小希的迷宫

2 并查集

• 无回路
• 单连通

并查集做，首先想到的是判断两个点是否连通，不连通就合并，已连通的话说明会形成回路，则可以判定 No，交了一发错了。
想了一下没有考虑到多个连通域的情况，该题必须只有一个连通域

3 树的性质

既然单连通无回路，则这肯定是一棵树；那么 edge=v-1;

题目链接：How Many Answers Are Wrong
思路参考：本题直接参考,图文解释

题目链接：Bear and Finding Criminals

大致题意就是小熊警察住在某个城市，他要抓各个城市的罪犯，现在用一个 BCD 可以知道那个城市里一定有罪犯。

一定能确定该城市有小偷的几种情况：

1. 警察所住城市有罪犯，则一定能检测到

2. 警察所住城市的左边和右边位置若都不为 0，则说明两座城市都有罪犯（只有一边为 1 是不能确定到底哪个城市有罪犯的）

3. 警察所在城市的一边检测到有罪犯，但在另一边已经没有城市了，则说明该城市一定有罪犯