洛谷 P3935 Calculating 题解
2024-09-07 09:28:58
一看我感觉是个什么很难的式子……
结果读完了才发现本质太简单。
算法一
完全按照那个题目所说的,真的把质因数分解的结果保留。
最后乘。
时间复杂度:\(O(r \sqrt{r})\).
实际得分:\(40pts\).
(实在想不到比这得分更低的算法了)
算法二
机智的发现是个因数枚举。
然后枚举因数。
时间复杂度: \(O(r \sqrt{r})\).
实际得分: \(40pts\).
(只是码量少一点)
算法三
推式子。
\(f_x\) 其实就是 \(x\) 的因数个数。
我们只需分别求出 \(\sum_{i=1}^r f_i\) 和 \(\sum_{i=1}^{l-1} f_i\) ,再相减即可。
(日常前缀和思路)
\[\sum_{i=1}^r f_i
\]
\]
\[= \sum_{i=1}^r \sum_{j|i} 1
\]
\]
\[= \sum_{i=1}^r \sum_{j=1}^i [j|i]
\]
\]
\[= \sum_{j=1}^r \sum_{i=1}^r [j|i]
\]
\]
(这步的依据是:我们不枚举每个数的因数,而是考虑每个数作为其它因数所产生的贡献)
\[= \sum_{j=1}^r \lfloor \frac{r}{j} \rfloor
\]
\]
(这步的依据是:从 \(1\) 到 \(n\) 共有 \(\lfloor \frac{r}{j} \rfloor\) 个数是 \(j\) 的倍数)
然后到这里,我们暴力枚举。
时间复杂度: \(O(r)\).
实际得分:\(60pts\).
算法四
暴力枚举个头?
答案摆在面前还在那暴力
明明是整除分块好吧。
不知道整除分块是啥?
\(\texttt{OK}\),你发现,这题竟然是 整除分块的模板题 。
时间复杂度: \(O(\sqrt{r})\).
实际得分:\(100pts\).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
inline ll read(){char ch=getchar();ll f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int main(){
ll l=read(),r=read();
ll ans=0; l--;
for(ll i=1,t;i<=r;i=t+1) {
t=r/(r/i); ll len=(t-i+1)%MOD;
ans=(ans+len*(r/i)%MOD)%MOD;
} //这是 1~r 的
for(ll i=1,t;i<=l;i=t+1) {
t=l/(l/i); ll len=(t-i+1)%MOD;
ans=(ans-len*(l/i)%MOD+MOD)%MOD; //这是 1~(l-1) 的
//为了防止模出负数,我们加上 MOD 再模
} printf("%lld\n",(ans+MOD)%MOD);
return 0;
}
最新文章
- ASP.NET Core应用的错误处理[1]:三种呈现错误页面的方式
- 【整理】Linux下中文检索引擎coreseek4安装,以及PHP使用sphinx的三种方式(sphinxapi,sphinx的php扩展,SphinxSe作为mysql存储引擎)
- mac系统上使用压缩包版的mysql(非安装版)
- ASP.NET MVC4+EasyUI+EntityFrameWork5权限管理系统——菜单模块的实现(二)
- 十条nmap常用的扫描命令
- 双系统重装windows后修复UBUNTU的GRUB
- Mellanox vma
- cxx-generator JS绑定工具
- PHP获取图片颜色值,检测图片主要颜色的代码:
- Ubuntu12.04 下修改Apache端口号
- 【转】sqlmap用户手册
- linux----LAMP之编译安装apache
- (转)关闭iptables和SELinux
- IScroll那些事——内容不足时下拉刷新
- .net 下发送calendar
- Discovery Scanning
- ES7的新特性
- Dom捕捉事件和冒泡事件-原理与demo测试
- grid网格的流动定位
- python面试题(二)