当前位置: 首页 > news >正文

P3601 签到题

// 容易注意到 qiandao(i) = i - phi(i)
// phi 是欧拉函数// 让我们想起最开始求欧拉函数的做法
// 分解质因数, 然后使用 phi(x) = x * 求积_{p in {x 的所有质因数}} (1 - 1 / p)
// 这样的时间复杂度显然过大// 我们何妨不反着思考
// 既然找到 l <= x <= r 的所有质因子不行, 不如考虑一个质因子是哪些 l <= x <= r 的质因子#include <iostream>
#include <vector>
using namespace std;
template <typename T>
using vec = vector<T>;#define int long longconst int N = 1e6 + 10;
vec<int> primes;
bool not_prime[N];// 线性筛模板
void get_primes(int n) {for (int i = 2; i <= n; i ++) {if (!not_prime[i]) {primes.push_back(i);}for (int j : primes) {if (i * j > n) break;not_prime[i * j] = true;if (i % j == 0) {break;}}}
}const int mod = 666623333;int l, r;vec<int> _pfactors[N];// 方便写代码的映射
// pfactors(i) 为 i 的质因子们
#define pfactors(i) _pfactors[(i) - l]signed main() {get_primes(N - 5);cin >> l >> r;// 我们可以遍历所有质数 p < sqrt r// 这里直接遍历所有 p < sqrt(r 的最大值) 了, 没差// 为什么是 p < sqrt(r)?// 对于一个数 x, 它的质因子中最多只会有一个大于 sqrt x// 这个质因子可以由 x 除以所有其他质因子得到// 可以想想分解质因数模板中为什么只用遍历到 sqrt x, 一个道理for (int p : primes) {// i 为 p 的 >= l 且 <= r 的倍数, 思想类似埃氏筛for (int i = ((l - 1) / p + 1) * p; i <= r; i += p) {pfactors(i).push_back(p);}}int ans = 0;for (int i = l; i <= r; i ++) {// 下面一段就是分解质因数, 只不过原本是遍历所有 <= sqrt x// 这里直接用提前求出来的 pfactorsint phi = i, x = i;for (int p : pfactors(i)) {phi = phi / p * (p - 1);while (x % p == 0) x /= p;}// 唯一一个大于 > sqrt(x) 的因子, 和分解质因数模板一样if (x != 1) phi = phi / x * (x - 1);ans = (ans + i - phi) % mod;}cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=35120

相关文章:

  • UOJ #1005. 【UR #32】王之钦定 题解
  • 图像采集卡重要功能解析:打通视频信号处理全链路
  • 2025年铣边机/铣床/刨边机/滚轮架/变位机厂家推荐排行榜,专业实力与市场口碑深度解析
  • 2025年通风天窗厂家最新权威推荐榜:排烟天窗、通风气楼、屋顶通风器、顺坡气楼、10A通风天窗、1型通风天窗、TC5A通风天窗、TC12B通风天窗、屋脊通风天窗专业选购指南
  • 【LeetCode】125. 验证回文串
  • YAML
  • QUALIFY 窗口过滤 - --
  • 【ffmpeg】开发过程中错误简单记录
  • 2025年冲压件厂家权威推荐榜:新能源/光伏/精密/异形/五金/铝/汽配/不锈钢/家具冲压件源头企业深度解析
  • AI 产品测试企业内训 | 两天构建企业级智能体测试能力
  • 详细介绍:《掰开揉碎讲编程-短篇》 2025 汉化idea控制台出现乱码解决方案 看完这篇解决不了乱码也是神人了
  • 探索无限可能:生成式推荐的演进、前沿与挑战【AI业务应用方向】
  • 【隐语SecretFlow架构解读】隐私保护模型在线推理系统 SecretFlow-Serving 架构解读
  • Excel学习指南
  • 2025 年宁波北仑仓库服务商推荐新世洋集团,港口物流仓储的专业之选宁波北仑仓库推荐
  • 2025年聚氨酯厂家权威推荐榜:浇注型聚氨酯/聚氨酯预聚体/聚氨酯胶黏剂/聚氨酯组合料/密封胶/胶辊/制品原料,源头厂家技术实力与产品应用深度解析
  • 02-02串口-单片机发送数据,电脑串口调试助手接收数据
  • 2025 矿物铸件源头厂家推荐榜:南通盟鼎新材料 5 星领跑,适配机床 / 电子 / 自动化设备基座需求
  • 3 大 Python 库助力高效 PDF 文件压缩 - E
  • 三麦克风阵列近场定位MATLAB实现(TDOA+GCC方法)
  • QOJ8233 题解
  • 2025年CNC高压清洗机厂家推荐排行榜:CNC全自动/数控高压清洗机、双工位/卧式清洗机、去毛刺/螺纹孔清洗机、工业/欧洲清洗机精选
  • 结对项目作业
  • 2025 年蒸汽发生器厂家最新推荐排行榜:电热 / 燃油 / 燃气 / 工业型设备实力企业深度解析
  • 2025 年国内锅炉厂家最新推荐排行榜:聚焦智能控制与稳定可靠的品牌深度解析电/蒸汽/燃气/燃油/电蒸汽锅炉公司推荐
  • 遗传算法入门
  • 关于keil5生成bin文件的方法
  • 2025 年食品级润滑油脂厂家最新推荐榜单:聚焦纳米材料技术突破,甄选核心竞争力突出的企业
  • 2025 年食品级润滑油源头厂家最新推荐排行榜:聚焦国产标杆企业,54 项专利加持,助力企业精准选品食品级润滑油液压油/食品级润滑油齿轮油/食品级润滑油烘焙设备润滑油厂家推荐
  • 2025年精密弹簧厂家权威推荐榜:压缩弹簧、拉伸弹簧、异形弹簧专业制造商实力解析与选购指南