Pistachio's Blog

Later equals never.

欧几里得

求最大公约数（最大公因子　GCD）质因数分解法例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。辗转相除法 gcd(a,b) = gcd(b,a mod b) 1234int gcd(in......

Posted by Liao on 2019-10-12

同余定理

定理同余,顾名思义是相同的余数,如果a mod m == b mod m,则说m为同余的模. 也可这样理解:m|(a-b),即(a-b)是m的整数倍. 给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。取模技巧若a>0 && b>0，......

Posted by Liao on 2019-09-28

数学定理

互质两个或多个整数的公因数只有1的非零自然数. 公因数只有1的两个非零自然数，叫做互质数. 互质的性质:（1）两个数的公因数只有1的两个非零自然数,叫做互质数；举例：2和3，公因数只有1，为互质数；（2）多个数的若干个最大公因数只有1的正整数，叫做互质数；（3）两个不同的质数，为互质数；（4）1和任何自然数互质。两个不同的质数互质。一个质数和一个合数，这两个数不是倍数关系时互质。不含相......

Posted by Liao on 2019-09-28

爬取软考网站实践

1. 基本要求爬取文字图像 2. 反爬虫正则表达式3.文字存入文档分词频统计接口参数 http://www.rkpass.cn/tk_jiexi.jsp?product_id=201905281544305456038&tixing=xuanze ...

Posted by Liao on 2019-09-25

python爬虫学习笔记

安装requests库pip install requests 12345import requestsr = requests.get("https://www.baidu.com")r.status_code #返回状态码r.encoding("utf-8")r.text #打印出首页内容百度360关键词提交12345678910i......

Posted by Liao on 2019-09-22

线段树

1.定义线段树（segment tree）是用来存放给定区间内对应信息的一种数据结构。线段树是二叉树，一个区间每次被折半往下分，所以往下查找，（二叉树的二分查找）最多lon2n次就能查找到。有两种操作： 1）求某段区间的和 2）修改某个区间的值 2.过程1）建立二叉树 2）剪枝部分 e.g.求区间[2,5]的和可以直接返回 return0，即不用对其以下的结点进行......

Posted by Liao on 2019-09-13

linux常用命令

SCP上传下载1.从服务器拉取文件夹到本地scp -r root@xx.xxx.x.xx:文件所在路径 /home/Document 2.从本地上传文件到服务器scp -r /home/Document root@xx.xxx.x.xx:/home/default 3.rsync文件压缩tar -xvf file.tar tar -xzvf file.tar.gz tar -xjvf f......

Posted by Liao on 2019-09-12

Bellman Ford

1.定义 Bellman-Ford 算法是一种用于计算带权有向图中单(一个)源(顶点)最短路径的问题（单源指的是只有一个起点）：给定一个起点，求它到所有结点的最短路径。Bellman-Ford 算法能适应一般的情况（即存在负权边的情况），V*E<10^7。 Bellman-Ford 算法采用动态规划进行设计，时间复杂度 O(V*E)，其中 V 为顶点数量，E 为边的数量......

Posted by Liao on 2019-09-04

欧拉函数

1. 欧拉函数对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。例如φ(8)=4，因为1,3,5,7均和8互质。对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1) 欧拉函数公式$$φ(x) = x \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times …..\times (1......

Posted by Liao on 2019-09-03

快速幂

快速幂模板 12345678910111213long long fastpow(long long x,long long n){ int base = x; int res = 1; while(n) { if(n&1) res = (res%mod * base%mod)%mod; b......

Posted by Liao on 2019-09-02