搜索结果
查询Tags标签： lfloor，共有 37条记录-
主元素问题与摩尔投票法、格雷码
一堆小玩意，放到一起。 题意：给定一个n个元素数列，保证有一个数\(a\)的出现次数超过\(\lfloor\frac n2 \rfloor\)，求这个数。 数据范围\(n<=3000000,a_i\le2147483647,\)时限0.5s，空间2M。 也就是说你就只开几个变量就行了。（虽然考试的时候有人拿hash玄学乱搞过…
2022/9/3 23:23:35 人评论 次浏览 -
[数学记录]CF896D Nephren Runs a Cinema
题意：给定 \(n=x+y+z\)，求满足以下要求的长度为 \(n\) 的序列的数目：序列由 \(x\) 个 \(1\)，\(y\) 个 \(-1\)，\(z\) 个 \(0\) 组成，序列任意前缀和非负，和在 \([l,r]\) 之间。 考虑确定 \(z\) 和序列和的方案数。 看做卡特兰数类似折线图考虑。则在不能过线的前提下…
2022/9/2 23:53:01 人评论 次浏览 -
leetcode-793. 阶乘函数后 K 个零
793. 阶乘函数后 K 个零 图床：blogimg/刷题记录/leetcode/793/ 刷题代码汇总：https://www.cnblogs.com/geaming/p/16428234.html 题目思路 首先我们令\(zeta(x)\)为\(x!\)末尾零的个数。根据172.阶乘后的零有\(zeta(x)=\sum_{k=1}^\infty\left\lfloor\frac{x}{5^k}\righ…
2022/8/28 23:25:30 人评论 次浏览 -
P8443 题解
前言 题目传送门！ 更好的阅读体验？ 普及组月赛第一题。别的题解语言有点高深，我补篇题解。 思路 显然，\(\lfloor \dfrac{l}{x}\rfloor, \lfloor \dfrac{l+1}{x}\rfloor, \cdots, \lfloor \dfrac{r}{x}\rfloor\) 是连续的整数。 而且，显然有 \(\operatorname{gcd}(c, …
2022/8/26 6:23:36 人评论 次浏览 -
万能欧几里得算法学习笔记
万能欧几里得算法 基本描述 对于一条直线 \(\dfrac {px+r}{q}\)，满足 \(p>0,q>0,r\in[0,q-1]\)，求解有关 \(\lfloor\dfrac {px+r}{q}\rfloor,x\) 的一些函数。 考虑在坐标系上考虑这条直线，从 \((0,0)\) 开始走。 定义当直线穿过一条形如 \(y=h(h\in\Z)\) 的横线…
2022/8/6 1:23:52 人评论 次浏览 -
【模板】扩展欧几里得算法
【模板】扩展欧几里得算法 void exgcd(int a, int b, int &g, int &x, int &y) {if (!b) x = 1, y = 0, g = a;else {exgcd(b, a % b, g, x, y);int t = x;x = y;y = t - a / b * y;} }如何理解 虽然不知道在推什么但是确实推出来了（？ \[\begin{aligned} \b…
2022/7/26 14:24:59 人评论 次浏览 -
Baby_Step_Gaint_Step(BSGS) 算法
\(BSGS\) 算法，又称 “北（\(B\)）上（\(S\)）广（\(G\)）深（\(S\)）” 算法，“拔山盖世”算法，可以在 \(O(\sqrt{n})\) 的复杂度内求解离散对数问题。题目描述： 给定质数 \(p\) 和整数 \(a, n\)，求最小的非负整数 \(m\) ，满足 \(a^m \equiv n(mod\ \ p)\) 。 算法…
2022/7/21 1:23:35 人评论 次浏览 -
SDSC2021 Day1
又是一年SDSC到但是我已经成为时代的眼泪啦 但我翻翻去年的笔记，好像就Day1写得还行，剩下几天就很摸 所以就只把Day1的笔记搬过来啦~（我才不会说临时起意搬笔记的原因是又有好题图了（当然不是））配套题单 质数筛 提供一种快速的分解质因数的方法： 在线性筛的时候可以…
2022/7/9 23:54:11 人评论 次浏览 -
邻项交换排序类贪心
原理论述部分引用自浅谈邻项交换排序的应用以及需要注意的问题 luogu题单 引言 邻项交换排序是一种常见的贪心算法，通过比较两个相邻元素交换前后的优劣对整个序列进行排序，从而使得这个序列成为题目所求的最优解。 然而，邻项交换排序的应用有一些需要注意的地方，稍有…
2022/7/3 23:26:44 人评论 次浏览 -
2022.6.28
SP26017 GCDMAT - GCD OF MATRIX比较傻逼的题目，显然答案等于 \[\large sum_{d=1}^n \varphi_d \times \lfloor \frac n d \rfloor \times \lfloor \frac m d \rfloor \]容斥+整除分块即可。SP26045 GCDMAT2 - GCD OF MATRIX (hard)和上题相同，不过数据范围变大了，要卡…
2022/6/28 23:32:20 人评论 次浏览 -
AcWing 199. 余数之和
题目传送门 零、参考资料 总结与思考：数论分块 【数学】数论分块（整除分块） 一、数论分块的相关概念 “数论分块”这个名词，其实比较模糊，没有一个广泛认同的严格定义。这里讲一下我个人的理解： 令\(\displaystyle f(i)=\lfloor \frac{n}{i} \rfloor\) \(f(i)\)的值…
2022/6/18 23:20:56 人评论 次浏览 -
模拟赛t3 太阳神(ra) 题解
太阳神 求满足如下条件的数对$(a,b)$对数:$a,b$均为正整数且$a,b \leq n$而$lcm(a,b)>n$。 答案对$10^9+7$取模 $n\leq 10^{10}$. 原题题解写的看不懂 题意即为求 $\sum _{a=1} ^{N} \sum _{b=1} ^{N} [lcm(a,b)>N]$. 转化为 $N^2-\sum _{a=1} ^{N} \sum _{b=1} ^{N…
2022/6/6 23:21:48 人评论 次浏览 -
[数学基础] 4 欧几里得算法&扩展欧几里得算法
欧几里得算法 欧几里得算法基于的性质：若\(d|a, a|b\)，则\(d|(ax+by)\)\((a,b)=(b,a~mod~b)\)第二条性质证明： \(\because a~mod~b=a-\lfloor \frac{a}{b} \rfloor\times b\)，令\(c=\lfloor \frac{a}{b} \rfloor\) 则问题等价于证明\((a,b)=(b,a-c\times b)\) 这个证明…
2022/5/10 11:02:32 人评论 次浏览 -
整除分块 学习笔记
板子题 板子题-UVA11526 题目大意： 给定一个 \(n\)，求 \(\sum\limits_{i-1}^{n}\lfloor \frac{n}{i} \rfloor\)。其中 \(n\) 为 \(32\) 位无符号整数。 题目解析 显然如果暴力求解肯定是不可行的，显然会 TLE，所以我们需要找一种复杂度更优的算法。 我们可以先令 \(n=1…
2022/4/25 23:15:57 人评论 次浏览 -
北大集训 / CTT 2021 部分题解
忘报名北大集训，还是能看到题，省了 8000 块钱，赢麻了。 鸽表示没代码，may be 无正解思路。 Day 1 A. 末日魔法少女计划 鸽。 \(k = 2\) 的做法：考虑分治，取中间点，处理所有跨过中点的，连上左右两边所有到这里的边，递归下去，是 \(O(n \log n)\) ，但是有很多重复…
2022/3/25 6:22:45 人评论 次浏览
