搜索结果
查询Tags标签： lfloor，共有 37条记录-
类欧几里得算法
类欧几里得算法 问题引入 设 \[f(a, b, c, n) = \sum_{i=0}^n \left\lfloor\frac{ai + b}{c}\right\rfloor \]其中 \(a, b, c, n\) 是常数，需要 \(\mathcal O(\log n)\) 的做法。 若 \(a \geq c\) 或 \(b \geq c\)，我们可以将 \(a, b\) 对 \(c\) 取模以简化问题。 考虑到…
2022/3/9 14:14:42 人评论 次浏览 -
【CF1601F】Two Sorts（Meet in Middle）
题目链接定义 \(a_{1\sim n}\) 为将 \(1\sim n\) 按字典序从小到大排序后的结果，求 \((\sum_{i=1}^n(i-a_i)\ \operatorname{mod}\ 998244353)\ \operatorname{mod}\ 10^9+7\)。 \(1\le n\le10^{12}\)题意转化 这题的求和中有两种不同的取模，看起来非常麻烦。 考虑取模的…
2022/3/8 23:19:25 人评论 次浏览 -
Darkbzoj 2818 Gcd
Darkbzoj 2818 Gcd 链接：https://darkbzoj.tk/problem/2818规定 \([x]\) 为逻辑判断函数，若 \(x\) 为真则 \([x]=1\)，否则 \([x]=0\) 。 这题要我们统计的是： \[\sum_{i=1}^{m}\sum_{j=1}^{\lfloor\frac{n}{p_i} \rfloor}\sum_{k=1}^{\lfloor\frac{n}{p_i}\rfloor}[gc…
2022/1/1 23:11:55 人评论 次浏览 -
Darkbzoj 2818 Gcd
Darkbzoj 2818 Gcd 链接：https://darkbzoj.tk/problem/2818规定 \([x]\) 为逻辑判断函数，若 \(x\) 为真则 \([x]=1\)，否则 \([x]=0\) 。 这题要我们统计的是： \[\sum_{i=1}^{m}\sum_{j=1}^{\lfloor\frac{n}{p_i} \rfloor}\sum_{k=1}^{\lfloor\frac{n}{p_i}\rfloor}[gc…
2022/1/1 23:11:55 人评论 次浏览 -
容斥原理
容斥原理 原型求n个相交的集合的元素总个数 原理例如：证明 设元素x在所有集合中出现了k次，然后写出等式，应用组合数恒等式例题 给定一个整数 n 和 m 个不同的质数 p1, p2, …,pm。 请你求出 1∼n 中能被 p1, p2, …,pm 中的至少一个数整除的整数有多少个。 例子如何计算…
2021/12/24 23:07:14 人评论 次浏览 -
容斥原理
容斥原理 原型求n个相交的集合的元素总个数 原理例如：证明 设元素x在所有集合中出现了k次，然后写出等式，应用组合数恒等式例题 给定一个整数 n 和 m 个不同的质数 p1, p2, …,pm。 请你求出 1∼n 中能被 p1, p2, …,pm 中的至少一个数整除的整数有多少个。 例子如何计算…
2021/12/24 23:07:14 人评论 次浏览 -
杜教筛
杜教筛作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)积性函数 若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。 常见积性函数：\(\mu()\) ——莫比乌斯函数。 \(\phi()\) ——欧拉函数。\…
2021/10/6 23:13:28 人评论 次浏览 -
杜教筛
杜教筛作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)积性函数 若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。 常见积性函数：\(\mu()\) ——莫比乌斯函数。 \(\phi()\) ——欧拉函数。\…
2021/10/6 23:13:28 人评论 次浏览 -
[loj138]类欧几里得算法
模板题 定义$\lfloor x\rfloor$表示小于等于$x$的最大整数，$\lceil x\rceil$表示大于等于$x$的最小整数 不难发现，若$a\in Z^{+}$且$b,x\in Z$，则$ax\le b\iff x\le \lfloor\frac{b}{a}\rfloor$、$ax\ge b\iff x\ge \lfloor\frac{b-1}{a}\rfloor+1$ 通过拉格朗日插值法…
2021/9/15 22:05:21 人评论 次浏览 -
[loj138]类欧几里得算法
模板题 定义$\lfloor x\rfloor$表示小于等于$x$的最大整数，$\lceil x\rceil$表示大于等于$x$的最小整数 不难发现，若$a\in Z^{+}$且$b,x\in Z$，则$ax\le b\iff x\le \lfloor\frac{b}{a}\rfloor$、$ax\ge b\iff x\ge \lfloor\frac{b-1}{a}\rfloor+1$ 通过拉格朗日插值法…
2021/9/15 22:05:21 人评论 次浏览 -
Codeforces 698F - Coprime Permutation（找性质）
Codeforces 题面传送门 & 洛谷题面传送门 u1s1 感觉这个 D1F 比某道 jxd 作业里的 D1F 质量高多了啊，为啥这场的 D 进了 jxd 作业而这道题没进/yun 首先这题肯定有个结论对吧，那么我们就先尝试猜一下什么样的排列符合条件，也就是先考虑这题 \(a_i\) 全是 \(-1\…
2021/9/1 23:37:00 人评论 次浏览 -
Codeforces 698F - Coprime Permutation（找性质）
Codeforces 题面传送门 & 洛谷题面传送门 u1s1 感觉这个 D1F 比某道 jxd 作业里的 D1F 质量高多了啊，为啥这场的 D 进了 jxd 作业而这道题没进/yun 首先这题肯定有个结论对吧，那么我们就先尝试猜一下什么样的排列符合条件，也就是先考虑这题 \(a_i\) 全是 \(-1\…
2021/9/1 23:37:00 人评论 次浏览 -
Codeforces Round #701 (Div. 2) A. Add and Divide
题目链接 目录题目大意题目分析AC代码 题目大意 给你两个数字\(a\)和\(b\)，让你执行两种操作：\(a=\lfloor \frac{a}{b}\rfloor\) \(b=(b+1)\)问你最少需要几次操作，让\(a\)变成\(0\) 题目分析 当\(a=10^9,b=1\)的极限情况下，最少操作次数不超过20次，之后再去暴力枚举…
2021/8/17 23:07:56 人评论 次浏览 -
Codeforces Round #701 (Div. 2) A. Add and Divide
题目链接 目录题目大意题目分析AC代码 题目大意 给你两个数字\(a\)和\(b\)，让你执行两种操作：\(a=\lfloor \frac{a}{b}\rfloor\) \(b=(b+1)\)问你最少需要几次操作，让\(a\)变成\(0\) 题目分析 当\(a=10^9,b=1\)的极限情况下，最少操作次数不超过20次，之后再去暴力枚举…
2021/8/17 23:07:56 人评论 次浏览 -
POJ2480
题目：求\(\sum\limits_{i=1}^{n}\gcd(i,n)\) \(\sum\limits_{i=1}^{n}\gcd(i,n)=\sum_{d\mid n}(d\times\sum\limits_{i=1}^n[\gcd(i,n)==d])=\sum_{d\mid n}(d\times\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(di,n)==d])\) \(=\sum_{d\mid n}d\ti…
2021/8/11 23:07:11 人评论 次浏览
