中国剩余定理C++实现
中国剩余定理C++实现笔者最近对中国剩余定理产生兴趣,遂以C++写为代码,在此记录一下。
1、中国剩余定理
中国剩余定理源于《孙子算经》,其具体在于解决以下形式方程:
$\begin{aligned}&\begin{cases}x\equiv a_1(modm_1)\x\equiv a_2(modm_2)\x\equiv a_3(modm_3)\…\x\equiv a_n(modm_n)\end{cases}\end{aligned}$
核心公式为:
$\begin{aligned}K=\prod_{j=1}^{n}m_{j},\quad x=\left[\sum_{i=1}^{n}a_{i}\times\frac{K}{m_{i}}\times(\frac{K}{m_{i}})^{-1}(modm_{i})\right]modK\end{aligned}$
2、C++代码实现
要实现以上公式 ,需要两部分,一是算出公式中乘法逆元部分,二是完成公式主体部分计算。乘法逆元部分使用扩展欧几里得算法,代码如下:
1int ex_gcd( ...
线性筛素数的Python实现
线性筛素数的Python实现转载线性筛法 - _NachoNeko - 博客园 (cnblogs.com)
用于筛选素数
12345678910111213141516171819202122232425def sieve_of_eratosthenes(n): """ 返回小于等于 n 的所有素数 """ is_prime = [True] * (n + 1) is_prime[1] = False primes = set() # 存储素数的集合(列表之类都行) for i in range(2, n + 1): if is_prime[i]: # i 是素数,将其添加到素数列表中 primes.add(i) # 用素数 i 来筛去它的倍数 for prime in primes: # 如果素数 prime 的平方大于 i,则跳出循环 # 因为 p ...
线段树的python实现
线段树的python实现求区间和,区间最值等
博客博客1: 线段树 从入门到进阶
博客2:线段树详解
博客3
题目地址落谷:
P3374 【模板】树状数组 1
P3368 【模板】树状数组 2
基本概念
什么是线段树线段树是一种二叉搜索树,什么叫做二叉搜索树,首先满足二叉树,每个结点度小于等于二,即每个结点最多有两颗子树,何为搜索,我们要知道,线段树的每个结点都存储了一个区间,也可以理解成一个线段,而搜索,就是在这些线段上进行搜索操作得到你想要的答案。
线段树能够解决什么样的问题线段树的适用范围很广,可以在线维护修改以及查询区间上的最值.每次更新以及查询的时间复杂度为O(logN)
线段树的空间使用在优化之前,线段树是有空间没有使用的,因此需要4*n(n为数组大小)个节点来储存数据
线段树的下标关系因为他是一棵完全二叉树,因此满足如下下标关系(下标从1开始)
l = fa*2 (左子树下标为父亲下标的两倍)
r = fa*2+1(右子树下标为父亲下标的两倍+1)使用位运算的话是如下的表示关系
k<<1(结点k的左子树下标) : k*2
2k<&l ...
用Python实现欧拉筛
用Python实现欧拉筛123456789101112131415161718192021222324252627282930313233343536373839404142N = 1000010 def get_prime(): global cnt for i in range(2,n+1): if not st[i]: cnt += 1 # 不管是合数还是质数,都用来筛掉它的倍数 for j in range(i,n+1,i): st[j] = True def get_prime_egypt(): global cnt for i in range(2,n+1): if not st[i]: cnt += 1 # 可以用质数就把所有合数筛掉 for j in range(i,n+1,i): st[j] = True # 保证n只会被它的最小质因子筛掉(埃式筛 ...