UVA294 约数 Divisors 题解
2024-09-05 18:52:09
Content
给定 \(n\) 个区间 \([l,r]\),求出每个区间内约数个数最大的数。
数据范围:\(1\leqslant l<r\leqslant 10^{10}\),\(r-l\leqslant 10^4\)。
Solution
你可能需要在做这题目前了解一下约数个数定理。何谓约数个数定理?
设一个数 \(x\) 的个数可以分解为若干个质因数相乘的积,即:
\[x=\prod\limits_{i=1}^k p_i^{a_i}
\]
\]
那么 \(x\) 的约数个数 \(f(x)\) 有一个这样的式子:
\[f(x)=\prod\limits_{i=1}^k(a_i+1)
\]
\]
如何证明?很简单,我们由约数定义可知,\(p_1^{a_1}\) 的约数有:\(p_1^0,p_1^1, p_1^2,\dots,p_1^{a_1}\),共 \(a_1+1\) 个。同理 \(p_2^{a_2}\) 的约数有 \(a_2+1\) 个……以此类推,\(p_k^{a_k}\) 的约数有 \(a_k+1\) 个。因此,由乘法原理可知,\(x\) 的约数个数就是 \((a_1+1)(a_2+1)\dots(a_k+1)=\prod\limits_{i=1}^k(a_i+1)\)。
那么思路就非常清晰明了了:
- 预处理出 \(\sqrt{10^{10}}\) 以内的所有质数,可以用埃氏筛也可以用线性筛。
- 注意到 \(r-l\leqslant 10^4\),因此我们考虑直接从 \(l\) 到 \(r\) 枚举每一个数。
- 枚举每一个数时,我们枚举每一个质数,一旦发现这个质数是当前枚举到的数的因子,我们就不断地将当前枚举的数除以这个质因子,直到这个质数不再是当前述的因子为止。
- 设我们除了 \(num\) 次,然后我们往当前枚举的数的约数个数(初始化为 \(1\))去乘 \(num+1\)。当前数的质因子分解完了以后再和当前的答案比较,并更新答案。
Code
namespace Solution {
int cnt, isprime[100007], prime[100007];
iv ai_prime() {
F(int, i, 2, 100000) isprime[i] = 1;
F(int, i, 2, 100000) if(isprime[i]) Fo(int, j, i * 2, 100000, i) isprime[j] = 0;
F(int, i, 2, 100000) if(isprime[i]) prime[++cnt] = i;
}
iv Main() {
ai_prime();
MT {
ll l = Rll, r = Rll, ans = 0, res = l;
F(ll, i, l, r) {
ll p = i, num = 1;
for(int j = 1; j <= cnt && prime[j] <= p; ++j) {
ll t = 0;
while(prime[j] && !(p % prime[j])) p /= prime[j], t++;
num *= (t + 1);
}
if(num > ans) res = i, ans = num;
}
printf("Between %lld and %lld, %lld has a maximum of %lld divisors.\n", l, r, res, ans);
}
return;
}
}
最新文章
- nodejs pm2部署配置
- mssql查询列名中包含特定字段的列
- TCP状态
- webView(简单的浏览器)
- div高度自适应(总结:min-height:100px; height:auto;的用法)
- [置顶] 《算法导论》习题解答搬运&;&;学习笔记 索引目录
- hdu4939 动态规划
- 解决64位win7系统IIS7[ODBC 驱动程序管理器]未发现数据源名称并且未指定默认驱动程序
- 【转】如何优化Cocos2d-X游戏的内存
- HDOJ(HDU) 2143 box(简单的多次判断-用的卫条件)
- Linux环境下使用JFS文件系统
- 开涛spring3(4.2) - 资源 之 4.2 内置Resource实现
- bbs论坛流程
- Awesome-3d
- HDU1007.Quoit Design
- Qt编写数据库通用翻页demo(开源)
- php实现Facebook风格的 time ago函数
- Haskell语言学习笔记(54)Data.Set
- Internet History, Technology and Security (Week 4)
- js学习笔记12----json数据格式,语法,遍历
热门文章
- 下一代的 3D Tiles 前瞻
- 查询多个count展示结果
- Yarp 让系统内调度更灵活
- DPC++中的现代C++语言特性
- Codeforces 997E - Good Subsegments(线段树维护最小值个数+历史最小值个数之和)
- 【豆科基因组】鹰嘴豆Chickpea (Cicer arietinum L.)429个自然群体重测序2019NG
- 认识Influxdb时序数据库及Influxdb基础命令操作
- dlang 字符串char[] 和string
- Linux-root管理员创建新用户
- Linux命令行批量删除文件(目录)