BZOJ 4173 数学

发布于 2017-04-13  254 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4173

题意:求出下式$$\varphi (n)*\varphi (m)*\sum_{k\in S(n,m)}^{ }\varphi (k)mod\ 998244353$$


$$m\ mod\ k+n\ mod\ k\geq k$$即$$n-\left \lfloor \frac{n}{k} \right \rfloor *k+m-\left \lfloor \frac{m}{k} \right \rfloor *k\geq k$$

所以等价于$$\left \lfloor \frac{m+n}{k} \right \rfloor-\left \lfloor \frac{m}{k} \right \rfloor-\left \lfloor \frac{n}{k} \right \rfloor=1$$

实际上,上式只能等于 0 或 1

所以$$ans=\sum_{k=1}^{n+m} \varphi (k)*\left \lfloor \frac{m+n}{k} \right \rfloor-\sum_{k=1}^{n} \varphi (k)*\left \lfloor \frac{n}{k} \right \rfloor-\sum_{k=1}^{m} \varphi (k)*\left \lfloor \frac{m}{k} \right \rfloor$$

另外我们还有一个性质,一个数的因数的欧拉函数和等于它本身,下面蒟蒻博主给出可能错误或很麻烦的证明 qwq(数学归纳法)

求证:$$n=\sum_{p|n}^{ }\varphi (p)$$

(然而证明未完成,下面给出思路)

首先当 n=1 时,显然成立。我们令 n=p 时成立,考虑倍增它,在 n=pd 时是否成立。

若 gcd(p,d)=1 那么 (此处讨论一种情况) 若 gcd(p,d)!=1 (讨论一种情况)

证毕啦啦啦

那么再推一推 (蒟蒻博主此处偷懒,剩余步骤并不困难,日后可能补全),就可以得到$$ans=\varphi (n)*\varphi (m)*n*m$$

代码如下

本题解部分改编自 这个博客


一个非常弱的准退役OIER