首页 > 其他分享 >3-smooth 数相关

3-smooth 数相关

时间:2023-04-30 20:14:29浏览次数:48  
标签:le 正整数 题解 可以 smooth Young 相关

算是 OI 弱相关的东西(?

因为见到了好几个可以这么嗯搞的东西,所以发出来看看。

3-smooth 数

如果一个正整数的所有素因子均不大于 \(3\),我们称之为 3-smooth 数。

容易发现,3-smooth 数的一个等价定义就是能表示成 \(2^x3^y\) 的数,其中 \(x,y\in\mathbb N\)。

你可以在 OEIS A003586 中看到若干 3-smooth 数,以及相关的近似级别等信息。这里摘录其的前若干项:\(1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96\)。

对于任意一个正整数 \(n\),其总可以分解成 \(2^x3^yz\) 的形式,其中 \(2\nmid z\land3\nmid z\),也即可以分解成一个 3-smooth 数乘上 \(z\),其中 \(z\bmod6\in\{1,5\}\)。

这样我们就可以以 \(z\) 为代表元来划分等价类了。

即,当我们要考察 \(\le n\) 的所有正整数时,我们可以枚举 \(z\),然后对剩余部分的 3-smooth 数进行考虑,容易发现也就是 \(\lfloor n/z\rfloor\) 内的所有 3-smooth 数。

当要考察 \(\le n\) 的所有 3-smooth 数时,我们可以把其画成 Young 表的形式来考虑。

即,注意到当 \(y\) 增加 \(1\) 时,可能最大的 \(x\) 必定会恰好减少 \(1\) 或者 \(2\)。

譬如,如果我们要考察 \(\le100\) 的所有 3-smooth 数,可以画成这样的形式:

\[\begin{matrix}1&2&4&8&16&32&64\\3&6&12&24&48&96\\9&18&36&72\\27&54\\81\end{matrix} \]

也就是前面所摘录的那些项。

容易发现使用这个形式我们就可以估计 \(\le n\) 的 3-smooth 数的数目级别了。毛估估大概就是 \(\frac{\ln^2n}{2\ln2\ln3}+O(1)\) 的样子。

例题

因为实在没啥知识点,直接丢例题了。

bzoj2734 [HNOI2012]集合选数

枚举 \(z\),直接对着 Young 表的一列状压就完了。

复杂度是容易分析的。

SPOJ SUMMING

神秘题,可以看这篇题解

题解里给出了对第 \(n\) 项求取的一个不错的近似。

八校联考题 约树

这道题目就把上面那个 Young 表的作用体现得淋漓尽致了。

题解:【数据删除】

啥时候那题公开了再补吧。/shui/shui/shui

标签:le,正整数,题解,可以,smooth,Young,相关
From: https://www.cnblogs.com/myee/p/3-smooth-number.html

相关文章

  • 解决项目编译对SVN依赖的相关问题
    一、背景软件打包发布并在机器部署后并生命周期没有结束,后续会随着使用发现各种各样的Bug,整个生命周期都与Bug为伴,发现Bug并解决Bug就是软件产品的一部分,通常软件出现异常会有日志记录,当问题出现后,如何知道一个软件库的版本,从而快速从源码库拉取对应版本的源码,调试并修复呢?这就需......
  • 深度特征融合相关论文(后续更新)
       FCN:FullyconvolutionalNetworksforSemanticSegmentation—CVPR2015ResNet:DeepResidualLearningforImageRecognition—CVPR2016FPN:Featurepyramidnetworksforobjectdetection—CVPR2017DenseNet:DenselyConnectedConvolutionalNetworks—CVP......
  • pip和conda的源管理相关操作
    一、pip使用pip默认的镜像在国外,网络连接较差,下载速度比较慢D:\pythonProject3\Django>pipinstallDjango==2.1.3CollectingDjango==2.1.3DownloadingDjango-2.1.3-py3-none-any.whl(7.3MB)|█████████████|3.0MB15kB/set......
  • web安全基础-渗透相关字段
    1、Set-Cookie和cookies2、csp3、x-frame-option4、x-xss-frame5、location6、referer和origin7、user-agent、xff作为sql注入参数点、收集用户信息8、server、x-powered-for收集服务端信息9、cors......
  • 量子相关计算基本操作
    NOT,SWAPC-NOT量子门量子门NOT门NOT:输入与输出相反。量子门SWAP门SWAP:交换两个输入量子门C-NOT门 C-NOT:Controlled-NOT根据控制位决定输入是否变为相反的值。控制位为0,输出为目标值原值;控制位为1,输出为目标值的非值。此过程控制位的值保持不变。 C-NOT门中,控制位也......
  • Unity2020.1新功能探路:Profiler相关更新
    洪流学堂,让你快人几步。你好,我是你的技术探路者郑洪智,你可以叫我大智。大智作为探路者带你一块探索一下Unity2020.1里面有什么好玩的东西。这一次Profiler的更新比较大,咱们专门用一篇来看看Profiler方面的更新。主要包含以下几个方面:Profiler作为单独程序启动ProfileAnalyer包的更......
  • 纯记录-后台刷新页面相关改动点
    jq(window).bind('beforeunload',function(){if(true){//dosomethingreturn"areyousureleaving"}else{//dosomethingelse}})vartabbarcloseId=parent.xtabbar.tabbar.attachEvent("......
  • 代理服务修改postbody内容相关问题
    1.如果修改了postForm的内容,那么需要同步修改请求的contentType的值,对于go来说需要修改的是request.ContentType里的值以下是源码中关于contenType字段的注释ContentLengthrecordsthelengthoftheassociatedcontent.Thevalue-1indicatesthatthele......
  • 端口进程查看相关linux命令
    硬盘使用情况df-lh查看内存占用free-mhcat/proc/meminfoMem:内存的使用信息Swap:交换空间的使用信息total:总计物理内存的大小。used:已使用物理内存。free:可用物理内存。shared:多个进程共享的内存总额。buffers/cached:缓存缓冲使用物理内存大小。availabl......
  • html表格相关属性
    <!DOCTYPEhtml><html>   <head>      <metacharset="UTF-8">      <title>表头标签</title>   </head>   <body>      <tablealign="center"border="1"cellpadding="0"......