挖掘机技术哪家强【数学】

tonyfang posted @ 2016年8月14日 07:14 in 随笔 with tags c++ OI , 238 阅读

【题目大意】

给出$f(i) = \sum_{(x, i)=1} x$,$g(i) = \sum_{x|i}f(x)$

多组数据$T \leq 1000$,给出$n(n \leq 10^9)$,求出$g(n)$。

【题解】

这是什么题啊。。?不会做

让我打个表先

然后就发现了奇怪的规律。$2f(i) = n \phi(i)$

啊然后我们预处理一下就可以搞定啦。

代码不想写。复杂度$O(T \sqrt{n})$

证明:首先$\phi(i)$除了$i=2$都是偶数,那么说明互质的数成对。

由于$(a, n)=1$可以推出$(n-a, n)=1$,所以每对的和为$n$,共有$\frac{\phi(i)}{2}$对。

那么$f(i) = \frac{\phi(i)n}{2}$啦!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter