題目鏈接：這里 題意：如題。 解法：對于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。