题解 U131347
Rui_R
·
·
个人记录
题目大意：给定正整数M，请找出一个正整数N，使 N<=M 且此时
[原题](https://www.luogu.com.cn/problem/U131347)
通过各种方法，你会发现 $\sum_{i=1}^{n}\limits [i|n] \times\varphi(i)=n$，然后答案就显而易见。
下面我们来证明这个结论。
前置知识：关于$\varphi$ 的一些性质。
1.若$n=p^c$ ，其中$p$ 是质数。
那么原式等于 $\sum_{i=0}^{c}\limits\varphi(p^i)
我们知道对于n=\prod{p_i^{c_i}}，有 \varphi(n)=n \prod{(1-\dfrac{1}{p_i})}
于是原式等于1+\sum_{i=1}^{c}\limits(p^i-p^{i-1})=p^c=n
于是，对于n=p^c ，有 \sum_{i=1}^{n}\limits [i|n] \times\varphi(i)=n
2.若\sum_{i=1}^{n}\limits [i|n] \times\varphi(i)=n ， m=p^c 且 n\bot p ，p 是质数。
\sum_{i=1}^{nm}\limits [i|nm] \times\varphi(i)=\sum_{i=1}^{n}\limits [i|n]\sum_{j=0}^{c}\varphi(i\times p^j)
由于n \bot p ， 且 \varphi 是积性函数
上式等于 \sum_{i=1}^{n}\limits[i|n]\sum_{j=0}^{c}\varphi(i)\times\varphi(p^j)=\sum_{i=1}^{n}\limits [i|n]\varphi(i)\sum_{j=0}^{c}\varphi(p^j)
看一眼之前推出的东西。
上式等于\sum_{i=1}^{n}[i|n]\varphi(i)\times m=nm
首先，对于 n=1 该式显然成立。
我们知道，任意n \ne 1 一定能被转成若干质数幂的乘积的形式，而对于任意质数幂该式成立，对于一个成立的 n 与一个与其互质的质数幂的乘积也成立。
可知，对于任意正整数，该式成立。