挖掘机技术哪家强【数学】
【题目大意】
给出$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}$啦！
2023年6月17日 13:52
With the assistance of the editorial and content teams, we supply you with the best web content on any topic imaginable.Pavzi Post is a startup founded by dedicated webmasters and bloggers who want to produce engaging pavzi.com material that is truthful, fascinating, and worth reading. We are more of a digital community where you can find various information, resources, and subjects about current events or news.