_潜伏

分类

NOIP真题(3) 其它(1) 学习笔记(3) 数学知识(4) 数据结构(1) 未归档(2) 杂谈(1) 模板(1) 算法竞赛-进阶指南刷题记录(4) 题解(3)

/ 注册

全部文章（共23篇）

浅谈 Miller-Robbin 与 Pollard Rho

前言与虽然都是随机算法，不过用起来是真的爽。算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。是一个非常玄学的方式，用于在的期望时间复杂度内计算合数的某个非平凡因子。事实上算法导论给出的是，是的某个最小因子，...

2019-08-01

0 1114

位运算

位运算 1.知识 bit 是度量信息的单位，包含0和1两种状态。计算机的各种运算最后无不归结为一个个bit的变化。符号含义 & 与 ...

2019-07-17

0 556

高一下期末考试划水记

Day -inf~0 Day -12~-10 明明知道要考试了，一看日期：哈，还有接近两周时间复习，不慌。 Day -3~-1 嗯怎么不知不觉一周就过去了，我TM还什么都没怎么复习啊（看来这次药丸）；不行，不能颓了，我要复习！话音未落，“pzy,来狼人杀吗？” 。。。 “肯定要啦！”...

2019-07-12

0 452

BZOJ 1053

题目 BZOJ1053 反素数原题传送门题目分析那么关于这道题，首先来了解一下这 \(4\) 个引理（大家可以自己推一推这些引理）：引理\(1\)：\(\left[1,N\right]\) 中最大的反素数，就是 \(\left[1,N\right]\) 中约数个数最...

2019-04-07

0 496

积性函数与狄利克雷卷积

积性函数定义积性函数是指一个定义域为正整数 $N$ 的算术函数 $f(n)$ ，有如下性质：$f(1) = 1$ ，且 $\forall a,b \in \mathbb{N}^{+} \quad $ 且 $\quad \gcd(a,b) = 1$ ，有 $f(ab) = f(a) f(b)...

2019-04-02

0 604

Contest Hunter 3101

题目 Contest Hunter 3101 阶乘分解原题传送门题目分析这里介绍一个本蒟蒻自己\(yy\)出来的方法。我们发现，对于某一个单个的整数\(n\)，若\(n\)能被某一个数\(x\)整除，那么我们可以看作\(++count[x]\)、且将\(n\)变为\(n/x\...

2019-03-30

0 539

POJ2689

题目 POJ2689 Prime Distance 原题传送门主要思路刚看到这题，心想：不就筛个 \(\left[2,U\right]\) 的质数表出来就可以了吗？一看数据范围： \(1<=L< U<=2147483647\) \(\cdots\) \(Woc\)，...

2019-03-30

0 517

浅谈 Miller-Robbin 与 Pollard Rho

前言 $Miller-Robbin$ 与 $Pollard Rho$ 虽然都是随机算法，不过用起来是真的爽。 $Miller Rabin$ 算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法，但是在选择多种底数的情况下，正确率是可以接受的。 $Pollard Rho$ 是一个非常玄...

2019-03-26

0 489

3.17爆零赛

前言好久没考过试了，居然考这么挫qwq。。。 T1 water 题目描述给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。（来源：[CQOI2009]中位数）【数据规模】对于30%的数据中，满足n≤1...

2019-03-24

0 431

数学知识（数论）（持续更新中...）

素数定义请自行百度。。。质数的判定 1. 试除法若一个正整数$N$为合数，则存在一个能整除$N$的正整数$T$，其中$ 2≤T≤\sqrt{N} $ 证明：略简易代码： bool prime_judge(int x) { if(x<2) return fals...

2019-03-24

0 477