长白崎の个人博客

欧拉函数 1 欧拉函数的定义 欧拉函数（Euler’s totient function），通常记为φ(n)，是一个与正整数n相关的数论函数。它表示小于或等于n的正整数中与n互质的数的个数。互质的意思是这些数的最大公约数（最大公因数）为1。 欧拉函数的计算公式是φ(n)=n×(1−1p1)×(1−1p2)×…×(1−1pk)φ(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots \times \left(1 - \frac{1}{p_k}\right)φ(n)=n×(1−p1​1​)×(1−p2​1​)×…×(1−pk​1​)其中，n可以分解为素数因子的乘积：n=p1a1×p2a2×…×pkakn = p_1^{a_1} \times p_2^{a_2} \times \ldots \times...

约数 试除法找约数 说明： Java代码模板（统计有多少个约数）： 12345678910static long solve(int a) { long ans = 0; for(int i = 1;i<=Math.sqrt(a);++i) { if(a%i==0) { ++ans; if(a/i!=i) ++ans; } } return ans;} Java代码模板（统计质约数的个数）： 12345678910111213141516171819202122232425262728293031323334import java.util.Scanner;/** * https://www.acwing.com/problem/content/4661/ * @author 长白崎 * @class["质因数", "数论"] * */public class Main { public static void main(String[] args) { // TODO Auto-generated method...

前缀和

均值不等式 （1）对实数a,b有a2+b2>=2ab(当且仅当a=b时取“=”号)，a2+b2>=−2ab(当且仅当a=−b时取“=”号)a^2+b^2>=2ab(当且仅当a=b时取“=”号)，a^2+b^2>=-2ab(当且仅当a=-b时取“=”号)a2+b2>=2ab(当且仅当a=b时取“=”号)，a2+b2>=−2ab(当且仅当a=−b时取“=”号) （2）对于非负实数a,b,有$a+b>=2\sqrt{ab},即{a+b \over 2}>=\sqrt{ab} $ （3）对非负实数a,b有a(a−b)>=2ab>=0a(a-b)>=2 \sqrt{ab} >=...

常见方法有： 试除法： 朴素筛法O(nlogn)O(nlogn)O(nlogn)： 埃氏筛法O(nloglogn)O(nloglogn)O(nloglogn)： 线性筛法O(n)O(n)O(n)： Java代码模板(朴素筛时间复杂度O(nlogn)O(nlogn)O(nlogn) 12345678910111213141516171819202122232425262728293031323334import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(primes(n)); } /** * 朴素筛法 */ static int primes(int n) { boolean st[] = ...

逆元 ≡符号的意思 在数学中，符号≡表示模同余的关系。当我们写a≡b(modm)a \equiv b \pmod{m}a≡b(modm)时，意思是a与b在模m下同余，也就是说它们除以m后得到相同的余数。换句话说，a和b的差是m的倍数。例如，17≡3(mod7)17 \equiv 3 \pmod{7}17≡3(mod7)表示17和3在模7下同余，因为它们相减得到的结果是7的倍数，即17−3=14=2×717 - 3 = 14 = 2 \times 717−3=14=2×7。 逆元的本质： 逆元的定义： 假设 a 除 b，且a和b都是整数，非浮点数，那么我们希望不做除法，因为取余数的话除法很麻烦，所以我们希望把除法变成乘法，希望找到一个数，使得a/b的余数 == ax%m。 即对于某一个b，我们能够找到一个数x，使得a/b和ax模m的余数相同的话， 则把x记作b的模m的逆元，记作b的-1次方； 即b的逆元， b的-1次方，是一个整数，是一个标记。即我们可以把所有a/b的情况转化为a*b的逆元的情况下 %...

互质 什么是互质： 互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。 在考虑两个区间互质的情况之前我们先考虑它的一个子问题，一个数x与一个区间[l,r]的互质问题。 处理这个问题，最简单的方法肯定是遍历区间，复杂度为O(n)，n为区间长度，显然太慢。 这时我们可以逆向思维，转换问题，我们可以考虑求不互质的个数，然后再用全部个数减去不互质的个数。 不互质也就是说，有公共的因子，如果把问题转换成求同有某个因子的数量，那就好处理， 比如如果计算都有因子2，设区间为[l,r]，那我们只要计算1~r的个数减去1~l-1的个数，也非常好算，只要r/2-(l-1)/2...

算法题型分析 DFS算法： 数据类模拟类算法题 地图模拟类算法题

正向代理和反向代理 一、代理 代理就相当于中间商,本来A和B是可以直接连接的,但是此时添加了一个C在中间,A跟B不直接连接,而是通过C作为中介进行连接。最常见的例子就是二手东,其实很多我们租房子时签约的人不是房子的真正房东,而是房东委托的中介,房东不想管事或者房子太多,只靠自己无法进行管理,所以才会通过中介(代理)进行处理,像蛋壳、自如这样的租房软件其实也是中介的一种,真正的房东是直接将房子委托给这样的第三方中介进行出租。 一个完整的请求是由: client(客户端) -> proxy(代理) -> server(服务端) 组成。 二、正向代理 正向代理: 顺着请求的方向进行的代理，即代理服务器它是由你配置为你服务，去请求目标服务器地址。 举例一:...

快速幂 说明： 快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以$$O(logn)$$的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。 让我们先来思考一个问题：7的10次方，怎样算比较快？ 方法1：最朴素的想法，7*7=49，49*7=343，… 一步一步算，共进行了9次乘法。 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。 但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。 方法3：先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。 模仿这样的过程，我们得到一个在$$O(logn)$$时间内计算出幂的算法，也就是快速幂。 Java模板(迭代法) 12345678910static long qpow(long a,int n){ long sum =1; while(n!=0){...