Min_25 筛
Min_25 筛yyb好神仙啊干什么用的可以在\(O(\frac{n^{\frac 34}}{\log n})\)的时间内求积性函数\(f(x)\)的前缀和。别问我为什么是这个复杂度要求\(f(p)\)是一个关于\(p\)的简单多项式，\(f(p^c)\)可以快速计算。怎么做啊首先我们需要对每个\(...
51nod 1965 奇怪的式子 —— min_25筛
题目：http://www.51nod.com/Challenge/Problem.html#!#problemId=1965推式子就同这里：https://www.cnblogs.com/yoyoball/p/9196092.html一开始想设 \( g(n,j) = \sum\limits_{i...
关于min_25筛的一些理解
关于min_25筛的一些理解如果想看如何筛个普通积性函数啥的，就别往下看了，下面没有的(QwQ)。下文中，所有的\(p\)都代表质数，\(P\)代表质数集合。注意下文中定义的最小/最大质因子都是默认所有质因子本质不同。即\(2*2*3*4*5*5\)的最小/次小质因子都是\(2\)，最大/次大质因子...
51nod1965. 奇怪的式子（min_25筛）
题目链接http://www.51nod.com/Challenge/Problem.html#!#problemId=1965题解需要求的式子显然是个二合一形式，我们将其拆开，分别计算 \(\prod_\limits{i = 1}^n \sigma_0(i)^i\) 与 \(\prod_\limi...
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）题面51NOD\[\sum_{i=1}^n\sum_{j=1}^nsgcd(i,j)^k\]其中\(sgcd\)表示次大公约数。题解明摆着\(sgcd\)就是在\(gcd\)的基础上除掉\(gcd\)的最小因...
[UOJ422][集训队作业2018]小Z的礼物——轮廓线DP+min-max容斥
题目链接：[集训队作业2018]小Z的礼物题目要求的就是最后一个喜欢的物品的期望得到时间。根据$min-max$容斥可以知道$E(max(S))=\sum\limits_{T\subseteq S}^{ }(-1)^{|T|-1}E(min(T))$那么只需要知道每个子集中最早得到的物品的期望时间即...
UOJ 188 【UR #13】Sanrd——min_25筛
题目：http://uoj.ac/problem/188令 \( s(n,j)=\sum\limits_{i=1}^{n}[min_i>=p_j]f(j) \) ，其中 \( min_i \) 表示 i 的最小质因子。令 \( g(n,j)=\sum\limits_{i=1}^{n}[i \i...
莫比乌斯反演/线性筛/积性函数/杜教筛/min25筛 学习笔记
最近重新系统地学了下这几个知识点，以前没发现他们的联系，这次总结一下。莫比乌斯反演入门：https://blog.csdn.net/litble/article/details/72804050线性筛筛常见积性函数及其代码：https://blog.masterliu.net/algorithm/s...
min-25筛学习笔记
Min_25筛简介\(\text{min_25}\)筛是一种处理一类积性函数前缀和的算法。其中这类函数\(f(x)\)要满足\(\sum_{i=1}^{n}[i\in prime]\cdot f(i)\)可以被\(\sum_{i=1}^{n}[i\in prime]\cdot i^k\)简单表示或者...
Min_25筛学习笔记
感觉好好用啊Luogu上的杜教筛模版题一发 Min_25抢到了 rank1$ Updated \ on 11.29 $被 STO txc ORZ踩爆啦前言$ Min$_$25$筛可以求积性函数的前缀和要求$ f(p_i)为一个多项式，f(p_i^{k_i})可以快速计算$以下部分暂时忽略$ 1$，即...
【UOJ#422】【集训队作业2018】小Z的礼物（min-max容斥，轮廓线dp）
【UOJ#422】【集训队作业2018】小Z的礼物（min-max容斥，轮廓线dp）题面UOJ题解毒瘤xzy，怎么能搬这种题当做WC模拟题QwQ一开始开错题了，根本就不会做。后来发现是每次任意覆盖相邻的两个，那么很明显就可以套\(min-max\)容斥。要求的就是\(max(All)\)，而每个集合...
Min_25 筛小结
Min_25 筛这个东西，完全理解花了我很长的时间，所以写点东西来记录一些自己的理解。它能做什么对于某个数论函数 \(f\)，如果满足以下几个条件，那么它就可以用 Min_25 筛来快速求出这个函数的前缀和。它是一个积性函数对于一个质数 \(p\) ，\(f(p)\) 的表达式必须是一个项数比较小的...
LOJ572. 「LibreOJ Round #11」Misaka Network 与求和 [莫比乌斯反演，杜教筛，min_25筛]
传送门思路（以下令\(F(n)=f(n)^k\)）首先肯定要莫比乌斯反演，那么可以推出：\[ans=\sum_{T=1}^n \lfloor\frac n T\rfloor^2\sum_{d|T}F(d)\mu(T/d)\]可以整除分块，但后面的东西怎么办呢？令\(G(T)=F*\mu\)，那么就有...
UOJ #188 Sanrd —— min_25筛
题目：http://uoj.ac/problem/188参考博客：https://www.cnblogs.com/cjoieryl/p/10149748.html关键是枚举最小质因子...所以构造的 S 与最小质因子有关。代码如下：#include<cstdio>#include<...
[复习]莫比乌斯反演,杜教筛,min_25筛
[复习]莫比乌斯反演,杜教筛,min_25筛莫比乌斯反演做题的时候的常用形式：\[\begin{aligned}g(n)&=\sum_{n|d}f(d)\\f(n)&=\sum_{n|d}\mu(\frac{d}{n})g(d)\end{aligned}\]实际上还有\[\begin...
【UOJ#188】Sanrd（min_25筛）
【UOJ#188】Sanrd（min_25筛）题面UOJ题解今天菊开讲的题目。(千古神犇陈菊开，扑通扑通跪下来)题目要求的就是所有数的次大质因子的和。这个部分和\(min\_25\)筛中枚举最小值因子有异曲同工之妙。min_25筛什么的戳这里并且这题并没有积性函数。所以我们先筛出质数个数。然后考虑如...
Min_25筛 学习小记
前言为什么叫学习小记呢？因为暂时除了模板题就没有做其他的东西了。（雾这个东西折磨了我一整天，看得我身不如死，只好结合代码理解题解，差点死在机房。（话说半天综合半天竞赛真是害人不浅）为了以后忘了再受荼毒，这里还是写一下，如果有人会看到的话，希望可以帮助到吧。（话说这个东西我已经拖了好久了啊！！！）（话...
Leetcode 155 Min Stack 小顶堆+栈,优先队列实现 难度:0
https://leetcode.com/problems/min-stack/#include <vector>#include <queue>#include <map>#include <iostream>using namespace std;...
https://stackoverflow.com/questions/10423781/sql-data-range-min-max-category
select phone,count(order_id) as c from table_recordgroup by phoneorder by c descSELECT CASEWHEN (age >= 10 AND age <= 20) THEN '10-20'WHEN...
数据结构作业——max_and_min（栈）
DescriptionTonyY 最近喜欢上了数学，今天他研究一个只有加号和乘号，运算数为整数， 大小在 1-9 之间的表达式，你可以任意地往里加括号，如何让表达式的值最大或 者最小？Input输入仅一行，为上述的算式，长度 n（1<=n<=200）,保证算式合法。Output输 出 添...