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