CF 776E 欧拉函数

题目链接：这里 题意：如题。 解法：对于f(n)，若自然数对(x,y)满足 x+y=n,且gcd(x,y)=1，则这样的数对对数为f(n) 证明f(n)=phi(n) 设有命题 对任意自然数x满足x < n，gcd(x,n)=1等价于gcd(x,y)=1 成立，则该式显然成立，下面证明这个命题。 假设gcd(x,y)=1时，gcd(x,n)=k!=1,则n=n’k,x=x’k,gcd(x,y)=gcd(x,n-x)=gcd(x’k,(n’-x’)k)=k,与假设gcd(x,y)=1不符，故gcd(x,y)=1时，gcd(x,n)=1。同理可证gcd(x,n)=1时，gcd(x,y)=1。 综上，f(n)=phi(n)。 下面那个函数意义就是 n的所有因数的欧拉函数之和，这个数其实就是n本身，不会证明。所以F_k(n)=phi(…phi(n))（求(k+1)/2次phi。