熠丶

未归档

题解(156)

/ 注册

做想做的事，见想见的人

全部文章 / 未归档（共32篇）

组合数

求\(n!\)中有多少个质因子p 方法一（非递归）结论：\(n!\)中有\((\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+…)\)个质因子p 时间复杂度：\(O(logn)\) int cal(int n,int p){ int ans=0; ...

数论

2020-02-14

0 590

Markdown 公式指导手册

转载于 https://www.zybuluo.com/codeep/note/163962 标签： Tutorial 点击跳转至 C***rkdown 简明语法手册，立刻开始 C***rkdown 编辑阅读器的记录和写作之旅！本文为 MathJax 在 C***r...

2020-02-13

0 960

欧几里得算法和扩展欧几里得算法

欧几里得算法（辗转相除法）求两个正整数的最大公约数，时间复杂度 O(logn)。欧几里得算法基于下面这个原理：设a,b均为正整数，则gcd(a,b)=gcd(b,a%b)。证明：设 a = kb + r，其中 k 和 r 分别为 a 除以 b 得到的商和余数。则有 r = a ...

数论

2020-02-13

0 2164

大整数运算

大整数的储存为了方便随时获取大整数的长度，一般都会定义一个int型变量len来记录其长度，并和d数组组成结构体。 struct bign{ int d[1000]; int len; bign(){ //初始化结构体 memset(d, 0, sizeof(d)); //fill...

数论高精度

2020-02-12

0 447

素数表的获取（埃氏筛和欧拉筛以及Meisell-Lehmer算法）

Eratosthenes筛法（埃氏筛）时间复杂度：O(nlogn) 思路代码 const int N=1e6+10; //表长 int prime[N],cnt=0; //prime数组存放所以素数，cnt为素数个数 bool st[N]; //false为素数 void get_p...

数论

2020-02-11

0 811

快速幂（a^b mod p）的模板（递归和迭代）

快速幂的递归写法 typedef long long ll; ll binaryPow(ll a,ll b,ll m){ if(m==1) return 0; if(b==0) return 1; a%=m; if(b&1) return a*binaryP...

快速幂

2020-02-11

0 769

二分法求凸多边形的外接圆最大半径

这是一道来自《算法笔记》的题目题目描述给定 N 个线段的长度，试将它们头尾相接（顺序任意）地组合成一个凸多边形，使得凸多边形的外接圆的半径最大，求该最大半径。其中 N 不超过 105 ，线段长度均不超过 100 ，要求算法中不涉及坐标的计算。考查内容二分算法的本质就是通过不...

2020-02-08

0 1255

C++STL中lower_bound() 和 upper_bound()二分查找

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。通常用sort函数从小到大排序。在从小到大的排序数组中， lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于n...

STL

2020-02-08

0 636

C++STL常见用法

1、string 概念：相当于char*的封装，理解为字符串 1.1.简单使用 /**C中定义字符串以及打印*/ char *ch="asdkajbf"; for(int i=0;ch[i]!='\0';i++) cout<<*(ch+i); /**C++...

STL

2020-02-06

0 465

由数据范围反推算法复杂度以及算法内容

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在107为最佳。下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择： n≤30, 指数级别, dfs+剪枝，状态压缩dp n≤100 => O(n3)，floyd，dp n≤1000...

2020-02-03

0 696