最新要闻
- 女生发烧考出618分:一蹦三尺高 挨个房间报喜
- 每日消息!ChatGPT漏洞 讲故事送Window11激活Key!
- 世界快播:刘慈欣谈ChatGPT:人类的无能反而是人类最后的屏障
- 今日热议:关于高考志愿填报,这些热点问题需要关注
- 推出长达7年:任天堂股东质疑Switch已逼近极限
- 实时焦点:苹果前总监炮轰App Store存在灰色地带 标准随心所欲
- 三乙醇胺油酸皂商品报价动态(2023-06-24)
- 救命一声吼!山洪暴发女子大喊提醒救下多名游客 世界讯息
- 索尼PS5串流掌机价格曝光:最高2100元能接受么?
- 全球视点!泰坦号观光潜艇“打破常规留名后世”,老板一语成谶片受热议
- 今日热门!Stable Diffusion模型发布新版本:生成图像以假乱真
- 钻石价格,突发“跳水”!未来还会更便宜?
- 泰坦号事故后:加拿大将展开事故调查
- 车主自曝差点被闷死在特斯拉Model X里 车门锁死 原因揭晓
- 蔡徐坤巡演新加坡站开票 《Hug me(remix版)》同日上线
- 每日简讯:4亿票房端午黑马:《消失的她》官宣海外定档
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
DZY Loves Math|全球即时看
题面
对于正整数 \(n\),定义 \(f(n)\) 为 \(n\) 所含质因子的最大幂指数。例如 \(f(1960)=f(23×51×72)=3,f(10007)=1,f(1)=0\)。给定正整数 \(a,b\),求下式的值:
\[\sum_{i = 1}^a\sum_{j = 1}^bf(\gcd(a,b))\]题解
在下文的推导中,为避免歧义,设 \(N = \min(a,b), M = \max(a,b)\),显然 \(N \le M\)。
\[\displaystyle \begin{aligned} & \sum_{i = 1}^N \sum_{j = 1}^M f(\gcd(a,b))\\= & \sum_{d = 1}^N f(d) \sum_{i = 1}^N \sum_{j = 1}^M \left[\gcd(i,j) = d\right] \\= & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \left[\gcd(i,j) = 1\right] \\ = & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \varepsilon(\gcd(i,j)) \\= & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \sum _{t \mid \gcd(i, j)} \mu(t)\\= & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \sum _{t \mid i \land t \mid j} \mu(t)\\\end{aligned}\]设 \(T = dt\),那么:
【资料图】
\[\displaystyle \begin{aligned} & \sum_{d = 1}^N f(d) \sum_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} \sum _{t \mid i \land t \mid j} \mu(t)\\= & \sum_{T = 1}^N {\left\lfloor\frac{N}{T}\right\rfloor} {\left\lfloor\frac{M}{T}\right\rfloor} \sum_{d \mid T} f(d) \mu(\frac{T}{d})\end{aligned}\]设 \(h = f * \mu\),那么原式可化为:
\[\displaystyle \sum_{T = 1}^N {\left\lfloor\frac{N}{T}\right\rfloor} {\left\lfloor\frac{M}{T}\right\rfloor} h(T)\]下面考虑求函数 \(h(n)\) 的值,首先对 \(n\) 进行质因数分解:
\[\displaystyle n = \prod_{i = 1}^m p_i^{c_i} \ ( \ p_i \in \mathbb{P}, c_i \ge 1 \ )\]发现可以把 \(h(n)\) 写成如下形式:
\[\displaystyle h(n) = \sum_{ab = n} f(a) \mu(b)\]考虑到莫比乌斯函数 \(\mu(n)\) 的性质:如果 \(n\) 中含有平方质因子那么 \(\mu(n) = 0\)。所以可以得出能产生贡献的 \(b\) 即满足 \(\mu(b) \ne 0\) 的 \(b\) 一定满足:
\[\displaystyle b = \prod_{i = 1}^m p_i^{d_i} \ ( \ p_i \in \mathbb{P}, _i \in \{0, 1\} \ )\]所以可以得出 \(f(a) = l \lor f(a) - l - 1\)。
设 $l = \max \limits_{i = 1}^m c_i,k = \sum \limits_{i = 1}^m \left[ c_i = l\right] $。接下来按 \(k \ne m\) 和 \(k = m\) 两种情况分类讨论 \(h(n) 的值\)。
当 \(k \ne m\) 时,按 \(f(a) = l\) 和 \(f(a) = l - 1\) 两种子情况讨论。
当 \(f(a) = l\) 时,设在 \(k\) 个满足 \(c_i = l\) 的质数中选了 \(t\) 个,在另外 \(m - k\) 个质数中选了 \(s\) 个,那么可以得出贡献为:
\[\displaystyle \begin{aligned} & \sum_{s = 0} ^ {m - k} \sum_{t = 0}^{k - 1} \dbinom{k}{t} \times l \times (-1) ^ {s + t} \times \dbinom{m - k}{s}\\= & \sum_{t = 0}^{k - 1} \dbinom{k}{t} \times l \times (-1) ^ {t} \sum_{s = 0} ^ {m - k} (-1) ^ {s} \times 1^{m - k - s} \dbinom{m - k}{s} \\= & 0\end{aligned}\]当 \(f(a) = l - 1\) 时,\(k\) 个满足 \(c_i = l\) 的质数中一定全部选上,设在另外 \(m - k\) 个质数中选了 \(s\) 个,那么可以得出贡献为:
\[\displaystyle \begin{aligned} & \sum_{s = 0} ^ {m - k} (l - 1) \times (-1) ^ {s} \times \dbinom{m - k}{s}\\= & \sum_{s = 0} ^ {m - k} (l - 1) \times (-1) ^ {s}\times 1^{m - k - s} \dbinom{m - k}{s} \\= & (l - 1) \times \sum_{s = 0} ^ {m - k} (-1) ^ {s}\times 1^{m - k - s} \dbinom{m - k}{s}\\= & 0\end{aligned}\]当 \(k = m\) 时,有 \(f(a) = l\) 和 \(f(a) = l - 1\) 两种子情况,可以得出贡献为:
\[\displaystyle \begin{aligned} & \sum_{s = 0} ^ {m - 1} (l) \times (-1) ^ {s} \times \dbinom{m - k}{s} + (l - 1) \times (-1) ^ {m} \times \dbinom{m - k}{m - k}\\= & \sum_{s = 0} ^ {m} (l) \times (-1) ^ {s} \times \dbinom{m - k}{s} - 1 \times (-1) ^ m\\= & - 1 \times (-1) ^ m \\= & (-1) ^ {m + 1}\end{aligned}\]综上可以得出 \(h(n)\) 的计算式:
\[h(n)=\begin{cases} 0 & k \ne m\\(-1)^{m + 1} & k = m\end{cases}\]下面考虑如何高效的预处理出 \(h(n)\) 的值。
考虑一下欧拉筛在筛出合数 \(\displaystyle n = \prod_{i = 1}^m p_i^{c_i} \ ( \ p_i \in \mathbb{P}, c_i \ge 1 , p_i < p_{i + 1})\) 时的路径:
\[p_m \rightarrow p_m^2 \rightarrow p_m^3 \rightarrow \cdots \rightarrow p_m^{c_m} \rightarrow \\p_{m - 1} p_m^{c_m} \rightarrow p_{m - 1}^2 p_m^{c_m} \rightarrow \cdots n\]也就是说一个合数被筛出的路径是按质因子从大到小的顺序筛出的,所以可以开三个数组 \(preCount,nowCount\) 和 \(factorCount\),分别记录当前数的最小质因子的幂次,其他所有质因子的幂次和本质不同的质因子的个数。
如果在筛的过程中,设 \(i\) 为当前筛的数, \(j\) 为枚举的质数,\(t = i \cdot j\),如果 \(j \nmid i\),也就是说 \(j\) 不是 \(i\) 的质因子,但是其是 \(t\) 的最小质因子,所以 \(nowCount[t] = 1\),但是 \(preCount[t]\) 的值要根据 \(nowCount[i]\) 和 \(preCount[i]\) 的值来考虑:如果两者相等,直接赋值即可;否则直接赋 \(-1\),也就是说现在这个欧拉筛上的路径上的数的质因子幂次不可能相等了。如果 \(j \mid i\),直接累加即可。
Code
#include typedef long long valueType;constexpr valueType maxN = 1e7 + 5;class LineSieve {public: typedef long long valueType; typedef std::vector container;private: valueType size; container minFactorList; container primeList; container preCount, nowCount, factorCount, data, sum;public: explicit LineSieve(valueType _size_) : size(_size_), minFactorList(_size_ + 1), preCount(_size_ + 1, 0),nowCount(_size_ + 1, 0), factorCount(_size_ + 1), data(_size_ + 1),sum(_size_ + 1) { primeList.reserve((size_t) std::floor(std::log((long double) (_size_ + 1)))); for (valueType i = 2; i <= size; ++i) { if (minFactorList[i] == 0) { primeList.push_back(i); minFactorList[i] = i; nowCount[i] = 1; preCount[i] = 0; factorCount[i] = 1; data[i] = 1; } for (auto const &iter: primeList) { valueType const t = i * iter; if (t > size) break; minFactorList[t] = iter; if (i % iter == 0) { nowCount[t] = nowCount[i] + 1; preCount[t] = preCount[i]; factorCount[t] = factorCount[i]; break; } else { nowCount[t] = 1; preCount[t] = (nowCount[i] == preCount[i] || preCount[i] == 0) ? nowCount[i] : -1; factorCount[t] = factorCount[i] + 1; } } } for (int i = 2; i <= size; ++i) if (nowCount[i] == preCount[i] || preCount[i] == 0) data[i] = (factorCount[i] & 1) == 1 ? 1 : -1; else data[i] = 0; std::partial_sum(data.begin(), data.end(), sum.begin()); } valueType ans(valueType x) const { if (x > size) throw std::range_error("Larger than Size."); if (x < 0) throw std::range_error("Too small."); return sum[x]; }};int main() { valueType T; std::cin >> T; LineSieve Euler(maxN); typedef std::function solveFunction; solveFunction solve = [&Euler](valueType N, valueType M) -> valueType { if (N > M) std::swap(N, M); valueType result = 0; valueType l = 1, r; while (l <= N) { r = std::min(N / (N / l), M / (M / l)); result += (Euler.ans(r) - Euler.ans(l - 1)) * (N / l) * (M / l); l = r + 1; } return result; }; for (int i = 1; i <= T; ++i) { valueType N, M; std::cin >> N >> M; std::cout << solve(N, M) << "\n"; } std::cout << std::flush; return 0;}
关键词:
DZY Loves Math|全球即时看
女生发烧考出618分:一蹦三尺高 挨个房间报喜
每日消息!ChatGPT漏洞 讲故事送Window11激活Key!
世界快播:刘慈欣谈ChatGPT:人类的无能反而是人类最后的屏障
今日热议:关于高考志愿填报,这些热点问题需要关注
缓存一致性如何保障
推出长达7年:任天堂股东质疑Switch已逼近极限
实时焦点:苹果前总监炮轰App Store存在灰色地带 标准随心所欲
三乙醇胺油酸皂商品报价动态(2023-06-24)
救命一声吼!山洪暴发女子大喊提醒救下多名游客 世界讯息
索尼PS5串流掌机价格曝光:最高2100元能接受么?
全球视点!泰坦号观光潜艇“打破常规留名后世”,老板一语成谶片受热议
DLang 与 C 语言交互
Apollo2.1.0+Springboot使用OpenApI
邮箱:微信企业域名邮箱给gmail或hotmail等域外邮箱发邮件被退回问题如何解决? 环球观焦点
今日热门!Stable Diffusion模型发布新版本:生成图像以假乱真
钻石价格,突发“跳水”!未来还会更便宜?
使用python发送sip协议的OPTIONS 热门
k8s 深入篇———— k8s 的pod[五]-全球播资讯
8. Java-AOP 面向切面编程
文心一言 VS 讯飞星火 VS chatgpt (46)-- 算法导论6.1 4题|全球热点评
泰坦号事故后:加拿大将展开事故调查
车主自曝差点被闷死在特斯拉Model X里 车门锁死 原因揭晓
蔡徐坤巡演新加坡站开票 《Hug me(remix版)》同日上线
来一打自建IP Proxy玩玩之Majora
kafka学习之五_多个磁盘的性能验证 世界快看点
Go——常用函数
每日速递:卷福的十年同学会
每日简讯:4亿票房端午黑马:《消失的她》官宣海外定档
冲入球场拥抱梅西小伙获释后道歉:我真不是没素质的人
世界观天下!新会绿美生态园票价(新会绿美生态园票价多少钱)
腾讯两大国民APP账号又打通了?QQ悄然支持微信登陆 环球精选
环球快报:调查称安卓更易上手:iPhone用户遇到问题概率高出58%
java 异常处理,事务管理,事务共用,事务传递 天天微头条
Go-闭包和defer|最新资讯
环球热资讯!Zen3清库存?突然冒出个很特别的锐龙5 5700
虚幻5打造!腾讯动漫《斗罗大陆2》今日两集首播 霍雨浩初入星斗大森林|每日观察
“空中出租车”亮相巴黎航展:可降落空间直径仅需15米-环球速递
古力娜扎曾遭换脸视频威胁勒索:不给钱就毁了你!
男生单曲循环《好运来》查出593分大哭:比平时多出50分 超常发挥
全球钻石价格较峰值暴跌18%:人造钻石市场规模不断扩大_全球视点
环球最新:甲亢遇到异食癖:法国男子一顿吃15人份 急了还吃石头木塞
全球热点评!公鸡突然从背后“偷袭”萌娃 飞起两脚踹倒在地 第二天端午节就被炖了
泰国和美国两地大量鱼类死亡 或与海洋升温有关 快看点
【技术积累】C语言中的指针【一】_世界百事通
Go-自定义数据类型(函数类型)详解
行业风险管理需求强烈
焦点信息:AMD RX 7800被逼急了!硬塞进去个“大胖子”
世界视点!一考生查分 全家一起喊出“666”:打算冲击复旦、交大
Kafka学习之四_Grafana监控相关的学习
一天吃透MySQL面试八股文 环球微速讯
什么是大模型? 每日热讯
内马尔在足球界的地位_内马尔的盘带水平在足球史上处于什么地位 全球要闻
【环球财经】伦敦金属交易所基本金属23日多数下跌_全球信息
白玉兰奖完整名单出炉 年初大热电视剧《狂飙》挂零陪跑-天天实时
中国高空开伞试验运载器发射连续成功:木星、天王星我们来了! 今日热讯
男子微信回了个“OK”表情 结果竟成被告!一点都不冤 速读
环球报道:尼康Z8新故障导致无法锁定镜头:官方承诺免费维修
【天天新要闻】读发布!设计与部署稳定的分布式系统(第2版)笔记10_自动化和缓慢的响应
无线路由器怎么连接电视(无线路由器怎么连接)
【环球新要闻】要考北大!汶川“敬礼娃娃”郎铮高考637分:15年前被埋20小时
关注:OPPO突然放弃自研芯片 真是因为没钱了?3000哲库人不信
看热讯:四川学霸女生高考712分查完分就睡觉、汶川“敬礼娃娃”郎铮637分
微软承认输掉“主机战争”:Xbox难以与竞争对手抗衡 每日头条
环球微动态丨特斯拉AI账号悄然上线:Dojo超级计算机下月开始生产
pro e
无牌产品硬刚国际大牌 就因为带货主播们买地建厂?
复兴号开进青藏铁路 提速至160公里/时 全程不到6小时
微软终于认怂!重新恢复Win11文件管理器经典功能
《人世间》赢麻!成最佳中国电视剧 雷佳音吴越分获白玉兰最佳男女主角_当前热门
“泰坦”号悲剧隐患早已埋下
2023年 年轻人被迫流行功能机了?-每日快看
全球快资讯丨【技术积累】Git中的基础知识【一】
世界信息:登录验证,JWT,过滤器,拦截器使用总结 2023
全球资讯:索尼时隔10年公布全新PS掌机Q!价格够低
焦点资讯:女孩没考好 和妈妈吵架后竟被丢高速:网友观点出奇一致
“4S店之王”破产离场 斯巴鲁中国重大变更:开始独资|当前焦点
大超险些成为007 环球快资讯
南漳县属于哪个省市_南漳县属于哪个市|每日速讯
今日快看!电影相约2000年(相约2000年)
imessage怎么设置不要钱_imessage怎么设置
Springboot web 项目开发流程梳理总结|世界讯息
今日热门!模型剪枝:让深度学习模型更好地应对不同的任务和环境
WEB安全-渗透测试-waf绕过信息收集_世界快看点
【独家焦点】“超人”亨利卡维尔有望成为007新片邦德扮演者:试镜效果棒极了
长安欧尚Z6新能源半年降价3万多 车主集体投诉
天天讯息:ASP.NET Core MVC 从入门到精通之缓存
全球时讯:文心一言 VS 讯飞星火 VS chatgpt (45)-- 算法导论6.1 3题
当前头条:【后端面经-Spring】Spring 中 bean 的生命周期)
美国国债收益率持续下跌,10年期国债收益率下跌8.90个基点 世界资讯
世界通讯!GPS靠边!北斗全球卫星导航系统星座部署完成3年 正突破毫米级甚至更小精度
【忠阳车评】固态电池量产难在哪 世界微资讯
【天天报资讯】微软爆料索尼PS6主机:2028年推出
光刻机一哥荷兰ASML:建立全自主半导体产业链几乎不可能!|环球热讯
K8S安装记录
《暗黑破坏神4》野蛮人双晕结算流分享 野蛮人双晕结算流怎么玩?
高考查分场面代入感太强 男生601分激动得满屋蹦跳:高中三年考最好的一次
重庆两案例入选全国职业教育产教融合典型案例_观天下
5人全部遇难 泰坦号残骸距离泰坦尼克号500米 快看点
【世界快播报】轴距超过Model Y 3.5秒破百 即将上市的起亚EV6到底行不行?