首页 > 其他分享 >CF1717E Madoka and The Best University

CF1717E Madoka and The Best University

时间:2024-02-26 21:00:15浏览次数:25  
标签:Madoka gcd limits University mid operatorname lcm sum Best

CF1717E Madoka and The Best University

简化题意

求 \(\sum \operatorname{lcm}(c,\gcd(a,b)) \thinspace (a + b + c = n \thinspace , a,b,c \in Z^+)\)。

做法

由于我们只要知道其中两个数的值就能确定第三个数,所以只需要枚举两个数即可,这里考虑枚举 \(c\) 和 \(a\)。设答案为 \(ans\),则:

\[ans = \sum\limits_{c=1}^{n-2} \sum\limits_{a=1}^{n-c-1} \operatorname{lcm}(a,\gcd(a,n - a - c)) \]

由辗转相减法,可得 \(\gcd(a,n - c) = \gcd(a, n - a - c)\),所以:

\[ans = \sum\limits_{c=1}^{n-2} \sum\limits_{a=1}^{n-c-1} \operatorname{lcm}(a,\gcd(a,n-c)) \]

直接去算不太好优化。发现 \(\gcd(a,n-c) \mid (n-c)\),所以可以考虑直接枚举 \(\gcd(a,n-c) = d\),而 \(a < n-c\),则 \(\gcd(a,n-c)\) 一定不会等于 \(n-c\)。所以:

\[\begin{aligned} ans &= \sum\limits_{c=1}^{n-2} \sum\limits_{d \mid (n - c)}^{d \neq n - c} \operatorname{lcm}(a,d) \sum\limits_{a=1}^{n-c-1} [\gcd(a,n-c) = d] \\ &= \sum\limits_{c=1}^{n-2} \sum\limits_{d \mid (n - c)}^{d \neq n - c} \operatorname{lcm}(a,d) \sum\limits_{a=1}^{n-c-1} [d \mid a, \gcd(\frac{a}{d},\frac{n-c}{d}) = 1] \\ &= \sum\limits_{c=1}^{n-2} \sum\limits_{d \mid (n-c)}^{d \neq n - c} \operatorname{lcm}(a,d) \times \varphi(\frac{n-c}{d}) \end{aligned} \]

先线性筛出 \(n\) 以内的数的欧拉函数值。这样直接算,枚举次数为:

\[\sum\limits_{i=1}^{n-2} d(n-i) = \sum\limits_{i=2}^{n-1} d(i) < \sum\limits_{i=1}^{n} d(i) \approx n \ln n \]

所以时间复杂度为 \(O(n \ln n)\),还要带一点算 \(\operatorname{lcm}\) 的常数,不过这无关紧要。

标签:Madoka,gcd,limits,University,mid,operatorname,lcm,sum,Best
From: https://www.cnblogs.com/gevenfeng/p/18035154

相关文章

  • CF1916E Happy Life in University
    关于我赛时线段树忘了开四倍空间导致白吃了一发罚时这档逝原题传送门约定\(x\)子树内的叶子称为\(x\)的叶子。与\(x\)颜色相同的点称为\(x\)的同色点或\(x\)色点。所有在\(x\)子树内的、到\(x\)的路径上(两端不含)没有\(x\)的同色点的\(x\)的同色点称为\(x\)......
  • P2870 [USACO07DEC] Best Cow Line G
    https://www.luogu.com.cn/problem/P2870字典序最小显然贪心,若当前串首比串尾小,则取串首;若当前串首比串尾大,则取串尾。那串首串尾一样呢?这个顺序显然会影响到后续操作。考虑继续往内递归,如果碰到一样的,那么当前取什么都无所谓;若碰到不一样的,我们肯定是要取更小的那一边,因为这样......
  • academy和college "University"
    一文告诉你academy和college区别FFF看世界2024-01-2221:41上海哈利波特中的学院就是Academy"Academy"和"College"在一些语境中可能有交叉使用,但它们通常表示不同类型的教育机构。这里是它们的一般区别:Academy(学院):"Academy"一词通常指的是一所高中或中......
  • BM25(Best Matching 25)算法基本思想
      BM25(BestMatching25)是一种用于信息检索(InformationRetrieval)和文本挖掘的算法,它被广泛应用于搜索引擎和相关领域。BM25基于TF-IDF(TermFrequency-InverseDocumentFrequency)的思想,但对其进行了改进以考虑文档的长度等因素。一.基本思想  以下是BM25算法的基本思想......
  • Unlocking the Secrets of AI and Machine Learning: Techniques, Tools, and Best Pr
    1.背景介绍人工智能(ArtificialIntelligence,AI)和机器学习(MachineLearning,ML)是当今最热门的技术领域之一。它们为我们提供了解决复杂问题和自动化任务的强大工具。然而,这些领域的知识和技能对于许多人来说仍然是一个陌生领域。本文旨在揭示AI和ML的秘密,提供有用的技术、工......
  • 浙江科技大学(Zhejiang University of Science and Technology)
    浙江科技大学(ZhejiangUniversityofScienceandTechnology)为浙江省属全日制本科高校,是一所具有硕士、学士学位授予权和外国留学生、港澳台学生招生权的特色鲜明的应用型省属本科高校,主校区位于杭州西湖区小和山高教园区,分校区位于安吉教科文新区,是教育部首批“卓越工程师教育培......
  • 信阳 信阳农林学院 Xinyang Agriculture and Forestry University 简 称信阳农林
    信阳农林学院外文名XinyangAgricultureandForestryUniversity简    称信阳农林·XinyangA&FUniversity(XYAFU) 历史沿革1910年(清宣统二年)学校在私立淮西中等学堂旧址(今汝南县城关)创建,校名为汝宁府中等实业学堂。1911年改称汝宁府官立甲种农业学校。1......
  • 洛阳师范学院Luoyang normal university
    洛阳师范学院是一所省属普通高等本科院校,位于千年帝都、牡丹花城、丝路起点——洛阳。学校地处伊水之滨,万安山下,东汉太学便发端于此。南望二程故里,传颂着程门立雪、鲁台望道的佳话;西望关林和世界文化遗产龙门石窟,绽放着世界文化遗产的璀璨光芒。学校前身是始建于1916年的河南省立......
  • 《convex optimization》——Stanford University open class
    202312151.Introductionmathematicaloptimizationleast-squaresandlinearprogramingconvexoptimizationexapmlecoursegoalsandtopicsnonlinearoptimizationbriefhistoryofconvexoptimizationmathmeticaloptimizationoptimizationproblemminimize......
  • 初中英语优秀范文100篇-024The Best Gift I've Ever Received -我收到的最好的礼物
    PDF格式公众号回复关键字:SHCZFW024记忆树1AmongallthegiftsIhavereceived,thehand-madescarffromJudyisthebestgiftI'veeverreceived.翻译在我收到的所有礼物中,Judy亲手制作的围巾是我收到的最好的礼物简化记忆围巾句子结构这个句子是一个简单句......