Royen_-CSDN博客

原创数论——唯一分解定理

唯一分解定理前言一、定理内容二、素数拆分1. 试除法2. Pollard-Rho算法三、应用参考资料前言定理：对所有素数 p 和所有整数 a，b，如果 p | ab，则 p | a 或 p | b （或两者都成立）证明：采用反证法。假设 p | ab，但 p ∤ a 且 p ∤ b。故gcd（a，p）= 1，gcd（b，p）= 1，故gcd（ab，p） = 1，而 gcd（ab，p） = p，矛盾，原命题成立。由上面这个定理我们发现，任意一个合数的素因子分解式都是唯一的。一、定理内容任何一

2021-10-03 18:53:22 3027

原创数论——整数分块

整数分块一、前言二、引理三、证明四、模板代码一、前言在计算∑i=1n⌊ni⌋\sum_{i=1}^{n}⌊\frac{n}{i}⌋∑i=1n⌊in⌋的时候，枚举的时间复杂度是O(n)，当n很大的时候我们是无法接受的，由于[ni][\frac{n}{i}][in]中有很多重复的区间，所以我们需要一种更高效的算法。二、引理⌊ ⌋为向下取整符号引理1：任意整数a，b，c有 ⌊abc⌋=⌊⌊ab⌋c⌋⌊\frac{a}{bc}⌋=⌊\frac{⌊\frac{a}{b}⌋}{c}⌋⌊bca⌋=⌊

2021-10-03 18:41:48 305

原创数论——素数

素数一、定义二、定理三、素数判定试除法预处理法kn+i 法Miller-Rabin判定法前言前置知识算法流程四、素数的筛法参考资料一、定义素数（又称质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。1 既非素数也非合数，2 是唯一偶素数二、定理设 π ( x ) 为1到x中素数的个数由黎曼推导出下面的精确公式，详情见Riemann Prime Counting Function然后又有一个神奇的比式极限让我们得到如下结论：在自然数集中，小于n的质数有如下公

2021-08-12 21:22:01 1134

原创博弈论笔记总结

博弈论一、四大博弈模型1. 巴什博弈（Bash Game）2. 斐波那契博弈（Fibonacci Game）3. 威佐夫博弈（Wythoff Game）4. 尼姆博弈（Nim Game）二、使用步骤1.引入库2.读入数据参考资料一、四大博弈模型1. 巴什博弈（Bash Game）Problem一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。Solution结论：若n%(m+1)==0，则后手赢，否则先手赢。Proof若 n <= m

2021-08-10 20:22:55 3635

原创凸包问题（含叉积讲解）

凸包预备知识叉积1.概念的引入2.定义3.应用（1）求解三角形（平行四边形）面积（2）点定位（3）极角排序1.用叉积计算极角（精度高，时间慢）2.atan2函数（时间快，精度较差）凸包1.定义2.求解方法Graham's Scan法总结预备知识叉积1.概念的引入在平面中我们为了度量一条直线的倾斜状态，为引入倾斜角这个概念。而通过在直角坐标系中建立tan α = k，我们实现了将几何关系和代数关系的衔接，这其实也是用计算机解决几何问题的一个核心，计算机做的是数值运算，因此你需要做的就是把几何关系用代数

2021-08-01 16:55:53 1499

原创线性DP与背包DP

动态规划一、线性DP1.知识点（1）LIS（最长上升子序列）2.练习P1020 [NOIP1999 普及组] 导弹拦截二、使用步骤1.引入库2.读入数据总结一、线性DP1.知识点（1）LIS（最长上升子序列）分两种情况：1.子序列严格递增2.子序列非降实现方法O（n 2) 算法for(int i=2; i<=cnt; i++){ for(int j=1; j<=i-1; j++) { if(a[i]>a[j]) // 非降改为

2021-08-01 10:34:25 258

原创二分图匹配问题（未完待续）

匹配问题（学习笔记与例题）文章目录匹配问题（学习笔记与例题）前置知识一、二分图1. 定义2. 最大匹配增广路径3. 匈牙利算法HK算法（Hopcroft Karp算法）4. 二分图的判断实战应用[kuangbin带你飞]专题十匹配问题A - Fire NetB - The Accomodation of StudentsC - CoursesD - 棋盘游戏总结前置知识一、二分图1. 定义二分图又称作二部图，是图论中的一种特殊模型。设 G =（V,E）是一个无向图，如果顶点V可分割为两个

2021-05-31 21:04:15 190 1

原创 Max Sum Plus Plus HDU - 1024

Max Sum Plus Plus大致题意思路1.二维DP？2.滚动数组优化AC代码题目链接: Max Sum Plus Plus.大致题意给定m和n，将n个数分成m段（可不取完），求出m段和的最大值。1 ≤ n ≤ 1,000,000思路1.二维DP？定义dp[i][j] ：选取第 j 个数字的情况下将前 j 个数字分为 i 段的最大和。可分为两种情况：1.第 j 个数不独立成段： d[i][j-1]2.第 j 个数独立成段：d[i-1][k] ，其中 k=i-1，i，…，j

2021-05-08 21:56:18 106

原创 Just $h$-index HDU - 6482 （主席树 + 二分答案）

题目链接：Just h-index.大致题意给你一个长度为n的序列，有m个询问。每次询问 [L,R]区间中满足：区间中第k大的数大于等于k，求出最大的那个k。思路要求区间第k大的数，我们想到要用主席树。由于k值单调有界，故求最大的k可用二分答案解决。AC代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<string

2021-05-07 21:56:31 111

原创 Covering HDU - 6185 （递推+矩阵快速幂）

大致题意：用1 * 2规格的地毯去铺4 * n规格的地面，已知n，问有多少种不同的方案使得地面恰好被铺满且地毯不重叠。答案对1000000007取模。（1≤n≤1018)思路：考虑全部铺满时，前2列的放法。有如下5种情况：故可导出递推式AC代码：#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#define mod 1000000007us

2021-05-06 20:31:07 92

原创异或的性质及应用

异或的性质及应用前言一、性质二、运用三、例题前言最近写了几道关于异或的题，在这里总结一下性质一、性质（定义 : 0 ^ 0 = 0 , 1 ^ 1 = 0 , 1 ^ 0 = 1 , 0 ^ 1 = 1 )（就像不进位的加法）交换律结合律对任意数x，我们有：x ^ x=0 , x ^ 0=x自反性：a ^ b ^ b = a ^ 0 = a故 a ^ b ^ c = d ^ e <=> d = a ^ b ^ c ^ ea ^ b = (!a)

2021-04-22 21:48:16 613

原创 Tunnel Warfare HDU 1540

Tunnel Warfare HDU 1540Tunnel WarfareTunnel Warfare HDU 1540题目链接: [Tunnel Warfare](https://vjudge.net/problem/HDU-1540).大致题意解题思路难点解决方案总结题目链接: Tunnel Warfare.大致题意有n个点排成一列，每个点与相邻的点互相连通。现对区间【1，n】进行以下三种操作：破坏点x的联通性询问点x所处的最大连通区间的长度恢复最后被破坏的点联通性解题思路

2021-04-10 12:06:18 1353 6

Royen_的博客