裴蜀定理 在数论中，裴蜀等式是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a,b和m，关于未知数 x和y的线性丢番图方程（称为裴蜀等式）：ax+by=m 有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 x、y都称为裴蜀数，可用扩展欧几里得算法求得。 就是关于 x, y 的不定方程 ax + by =c 有整数解的充要条件是 gcd(a,b)∣c 。 题目见洛谷:P4549 模板 #include <cstdi…
简介 Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 无优化复杂度：O(n ^ 2) 那么有O（km）的Spfa算法我们为什么需要Dijkstra算法呢？ 因为某些毒瘤出题人会专门设计网格图来卡Spfa算法，使其变为O（m ^ 2）如下方提到的落谷题目。 洛谷：P3371（弱化版） Spfa能过 P4779（标准版）卡S…
简介 朴素的算回文串的办法一般是O（n ^ 2） 或 O（n ^ 3）的。而Manacher发明的马拉车算法能将空间复杂度和时间复杂度均优化到O（n）的线性。 具体算法过程是： 1、将字符串中加入# 如 abcde -> ##a#b#c#d#e 举个例子 一个字符串s = abbahopxpo，转换为$#a#b#b#a#h#o#p#x#p#o#（这里的字符 $ 只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#…
简介 Hash算法类似于给字符串进行加密的方式，方便判断重复 那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。 进制哈希是最常见（NOIP）的哈希方式 它的主要思路是选取恰当的进制，可以把字符串中的字符看成一个大数字中的每一位数字，不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是O(n) 评测：洛谷P3370 模板 #include <cstdio> #include <cstdlib> #include <…
逆元 a * b = 1 (mod p) 则a,b互为逆元 费马小定理 a ^(p-1) = 1 (mod p) p 为质数 -> a * a ^(p-2) = 1 (mod p) 于是 a和a ^(p-2) 互为逆元 欧拉函数 定义：φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) p(1),p(2)…p(n)为x的所有质因数 表示 小于x的数中与x互质的数的数目 欧拉公式：a ^ φ(p) =1 (mod p) -&…
问题模型 现在有一个这样的问题：有一个数组a，，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和。 这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O(1)的时间复杂度，而查询的话是O(n)的复杂度，总体时间复杂度为O(qn) 可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是O(1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O(n)，总体时间复杂度还是O(qn)。 可以发现，两种做法中，要么查询是O(…
题目描述 如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式： 第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。 接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。 输出格式： 一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647） 输入输出样例 输入样例#1： 4 6 1 1 2 2 2 3 2 …
一、安装Sublime Text3 由于官网最新的无法破解，我们需要使用较老版本 执行下列代码 wget https://download.sublimetext.com/sublime_text_3_build_3157_x64.tar.bz2 tar -xvvf sublime_text_3_build_3126_x64.tar.bz sudo mv sublime_text_3 /opt/ sudo cp /opt/sublime_text_3/sublime_text.desktop /usr/share/…
一、查看运行时间 头文件 #include<ctime> #include <ctime> #include <iostream> using namespace std; int main(){ int a,b; cin>>a>>b; int t=clock(); printf("%d\n",a-b); printf("Time："); cout << clock()-t << endl; …
