首页 > 其他分享 >一些 trick

一些 trick

时间:2023-08-06 20:24:00浏览次数:36  
标签:lfloor mu frac rfloor trick sqrt 一些 displaystyle

高次整除分块

对 \(\large\lfloor\frac{n}{i^2}\rfloor\) 整除分块,\(\large r=\sqrt{\lfloor\frac{n}{\lfloor\frac{n}{l^2}\rfloor}\rfloor}\).

容易发现对于 \(i\le n^{\frac{1}{3}}\) 和 \(i\ge n^{\frac{1}{3}}\),都只有 \(n^\frac{1}{3}\) 种取值,所以复杂度 \(O(n^{\frac{1}{3}})\).

对于更高次也是同理的。


\(\mu^2\) 的前缀和计算

详见 P9238 [蓝桥杯 2023 省 A] 翻转硬币.

对 \(i\) 进行唯一分解得 \(\displaystyle i=\prod p_i^{\alpha_i}\).

令 \(\displaystyle P=\prod p_i^{\lfloor\frac{\alpha_i}{2}\rfloor}\),那么 \(\mu^2(i)=1\Leftrightarrow P=1\).

那么 \(\displaystyle\mu^2(i)=\epsilon(P)=\sum_{d|P}\mu(d)\).

可以得到 \(\displaystyle\mu^2(i)=\sum_{d^2|i}\mu(d)\).

\[\sum_{i=1}^{n}\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^2}\rfloor \]

利用高次整除分块,可以对 \(\mu\) 线性筛或杜教筛。

杜教筛预处理 \(n^{\frac{2}{5}}\) 的前缀和可以做到 \(O(n^{\frac{2}{6}})\).


调和数求值

P1943 LocalMaxima

推出来的式子是第 \(n\) 个调和数 \(\displaystyle\sum_{i=1}^{n}\frac{1}{i}\).

有一个性质:

\[\gamma=\lim_{n\rightarrow\infty}(\sum_{i=1}^{n}\frac{1}{i}-\ln n) \]

右式是收敛的,\(\gamma\) 称为欧拉常数,近似值 \(0.57721566490153285\).

对于较大的 \(n\) 精度还是不错的。


差分前缀和优化函数求和

P9308 「DTOI-5」#1f1e33

已知函数 \(F\),求函数 \(G\) 满足

\[G(n)=\sum_{d=1}^{n}dF(\lfloor\frac{n}{d}\rfloor) \]

差分有

\[G(n)-G(n-1) \]

\[=\sum_{d=1}^{n}d\big(F(\lfloor\frac{n}{d}\rfloor)-F(\lfloor\frac{n-1}{d}\rfloor)\big) \]

所以对于 \(d|n\) 才会对 \(\Delta G\) 产生贡献。

这样时间复杂度从 \(O(n\sqrt{n})\) 优化至 \(O(n\log n)\).


完全平方数匹配

判断 \(a\times b\) 为完全平方数有一种简单的方法:

记 \(\displaystyle f(x)=\max_{d^2|x}d\),\(\displaystyle g(x)=\frac{x}{f^2(x)}\).

\(f^2(x)\) 也可以叫做 \(x\) 的最大平方因子。

那么 \(a\times b\) 为完全平方数即 \(g(a)=g(b)\).


带根号的整除分块

若 \(d^2k\in[l,r]\),那么 \(\displaystyle d\in[\sqrt{\frac{l}{k}},\sqrt{\frac{r}{k}}]\).

考虑怎么找到 \(\displaystyle\lceil\sqrt{\frac{l}{k}}\rceil\) 和 \(\displaystyle\lfloor\sqrt{\frac{r}{k}}\rfloor\) 相同的一段数。

对于 \(i\),找到最大的 \(j\) 应该是

\[\LARGE\lfloor\min\Bigg(\frac{l-1}{(\lceil\sqrt{\frac{l}{i}}\rceil-1)^2},\frac{r}{\lfloor\sqrt{\frac{r}{i}}\rfloor^2}\Bigg)\rfloor \]

好奇怪的渲染。

标签:lfloor,mu,frac,rfloor,trick,sqrt,一些,displaystyle
From: https://www.cnblogs.com/SError0819/p/17609926.html

相关文章

  • 一些笔记同步软件,notion替代,开源笔记软件
    StandardNotes|End-To-EndEncryptedNotesApphttps://www.bookstackapp.com/https://www.qownnotes.org/https://github.com/zadam/triliumFlowUs息流官网-新一代知识管理与协同平台,在线文档笔记知识库,项目管理协作Releases·toeverything/AFFiNE·GitHubAFFiNE......
  • trick : Trygub num
    trick大意我对于这个trick的理解为:支持位运算的高精度维护一个以\(b\)为基数的大数\(N\),并支持以下功能:给定(可能是负)整数\(|x|,|y|\leqslantn\),将\(xb^y\)加到\(N\)。\(N\geqslant0\)时,给定\(k\),打印\(N\)的第\(k\)位数字(指以\(b\)为基底意义下的)。检查\(N\)是正......
  • Mybatis-Flex 与 Mybatis-Plus 的一些对比
    为什么要引入Mybatis增强插件从一个业务开发者的角度来看,这种类似的增强框架使用起来很爽。单表情况下不必再把思路从Service切换到Mapper,从业务思维(业务流程)切换到数据库思维(数据库字段,编写),一定程度上减少了代码的开发量。易于维护数据库增改删字段不必再去xml里改,......
  • 一些简单数学小知识
    \[(a_1+a_2+a_3+...+a_n)^2=a_1^2+a_2^2+...+a_n^2+2a_1a_2+2a_1a_3+...2a_{n-1}a_n\]\[\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}\]证明:\[(n+1)^3=n^3+3n^2+3n+1\]\[(n+1)^3-n^3=3n^2+......
  • 使用VS时的一些报错_1
    一.使用EasyX库函数中的loadimage函数时报错:loadimage没有与参数列表匹配的重载函数解决方法:右键解决方案,点击属性,【高级】→【高级属性】右【字符集】设置成【使用多字节字符集】即可解决。二.错误C4996‘strcpy’:Thisfunctionorvariablemaybeunsafe.Considerusi......
  • Android学习笔记(三五):再谈Intent(下)-一些实践
    Android的UI框架要求用户将他们的app分为activity,通过itent来进行调度,其中有一个mainactivity由Android的launcher在桌面中调用。例如一个日历的应用,需要查看日历的activity,查看单个事件的activity,编辑事件的activity等等。在查看日历的activity中,如果用户选择的某个事件,需要通过......
  • Java性能监控的一些记录
    本篇所有内容都是基于JDK5,如使用JDK6会有差别。工作,有一些值得记录的地方:JDK自身提供了很多工具,基于命令行和GUI的都有,学会合理应用它们是很有用处的。首先是jmap,这是一个命令行程序,用来查看JVM中对象数量情况,直接输入jmap会显示用法,下面是两个常用的功能:Java代码 jmap-h......
  • 一些有趣的C++代码
    本文混合搅碎剁烂转载。。。 1:绘制曲线 #include<bits/stdc++.h>usingnamespacestd;intmain(){intx,m;for(doublei=1;i>=-1;i-=0.1){m=acos(i)*10;for(x=1;x<m;x++)cout<<"";cout<&l......
  • 对当下AI的一些观感思考
    目前来看,AI技术地震的震中还是在美帝那旮瘩。尤其是M7,这几家市值加总快15万亿美元了,个个都是行业翘楚,个个都有拿得出手的东西。AI是个技术密集、人才密集、计算密集的产业。美帝拥有全球一流的顶尖人才,以及财力、算力支持,生态市场也优势极大,无人能望其项背,包括咱们大天朝,这也是美帝......
  • js的一些写法
    1.用void0代替undefined不直接用undefined,因为undefined不是关键字,在函数中可以被变量占用,从而值发生变化,使用void(0)或void0,还好写一些2.用Number.isNaN代替isNaNisNaN很坑,判断不准,如下isNaN(undefined);//trueisNaN({});//trueisNaN("38,6")//true......