HDU 6417
2024-09-06 19:04:53
题意
做法
\(S_{a,b}\)为\(a\)与\(b\)中素数次幂奇偶性不同的集合,容易得出\[d_{a,b}=\left\{\begin{aligned}1 &&|S_{a,b}|=0\\
\prod_{p\in S_{a,b}}p&&|
S_{a,b}|\neq 0\end{aligned}\right.\]
用\(dis_{a,b}\)表示最短路,容易得出\[dis_{a,b}=\left\{
\begin{aligned}
1 &&|S_{a,b}|=0\\
\sum_{p\in S_{a,b}}p&&|S_{a,b}|\neq 0
\end{aligned}
\right.\]
考虑\(|S_{a,b}|=0\),把次幂为奇数的质因子拿出来,设乘积为\(c\),则\(a/c,b/c\)为不同的完全平方数,平方根在\([1,\sqrt{n/c}]\),故这部分答案为\[\sum\limits_{c=1}^n \mu(i)^2\binom{\sqrt{n/c}}{2}\]
考虑\(|S_{a,b}|=0\),对于每个质数\(p\),计算有多少对会用到它,设\(F(n)\)表示\([1,n]\)中有多少数含奇数个\(p\)
\[F(n)=\begin{cases}\left\lfloor n/p\right\rfloor-F(\left\lfloor n/p\right\rfloor)&n\ge p^2\\\left\lfloor n/p\right\rfloor&n<p^2\end{cases}\]
前者\(p\)较小可暴力算,后者值个数不多整除分块然后\(min25\)找区间素数个数即可
最新文章
- React反模式 —— 如何不使用JSX地动态显示组件
- Ubuntu下通过SSH远程登录服务器的方法
- vtk多线程简单测试
- ES6中的const命令【转】
- android 取消edittext焦点
- paramiko模块
- COM编程概述
- zip压缩包密码破解
- cocos2d-x3.x使用rapidjson
- animation-timing-function中的cubic-bezier(n,n,n,n)
- jcSQL词法分析器对字符串token的解析
- Oracle数据导入导出imp/exp(转)
- Android学习笔记:ListView简单应用--显示文字列表
- C#集合之有序列表
- .NET 体系结构(.net core、.net framework、xamarin之间的关系)
- 结对作业-基于GUI的四则运算
- 测试String.Format中的Format参数
- 多媒体管理器解析IMultimediaManager
- python 异步发送邮件 aiosmtplib
- 手把手教你利用Python自动下载CL社区图片
热门文章
- 文件图片上传目录 禁止执行php
- [jQuery]jQuery链式编程(六)
- ClientAbortException :客户端异常终止
- Cesium案例解析(四)——3DModels模型加载
- 「Spark」Spark SQL Thrift Server运行方式
- PythonI/O进阶学习笔记_10.python的多线程
- System.Text.Json 自定义Converter实现时间转换
- asp.net mvc 使用AuthorizeAttribute做授权验证
- Warning: curl_setopt() [function.curl-setopt]: CURLOPT_FOLLOWLOCATION cannot be activated when in safe_mode or an open_basedir is set…
- .net core 3.0 swagger