题解：CF776E The Holmes Children

原题链接

• 洛谷 CF776E The Holmes Children

解题思路

1. 化简 $f(n)$：

$$\begin{aligned} f(n) &= \sum_{i=1}^{n-1}[\gcd{(i,n-i)}=1] \\ &= \sum_{i=1}^{n-1}[\gcd{(i,n)}=1] \\ &= \sum_{i=1}^{n}[\gcd{(i,n)}=1] \\ &= \varphi(n) \end{aligned}$$

2. $f(n)=\varphi(n)$ 就是欧拉函数，而 $g(n)$ 是 $\varphi(n)$ 的和函数，即 $id(n)=n$：

$$\begin{aligned} g(n) &= \sum_{d\mid n}\varphi(d) \\ &= id(n) \\ &= n \end{aligned}$$

证明：$n$ 个分数 $\frac{1}{n},\frac{2}{n},\cdots,\frac{n}{n}$ 互不相等。考虑化简这些分数，得到新的 $n$ 个分数，他们的分母和分子互质，形如 $\frac{a}{d},d\mid a$ 且 $a$ 与 $d$ 互质。在所有 $n$ 个分数中，分母为 $d$ 的分数有 $\varphi(d)$ 个。所有不同分母的分数，其总数为 $\sum_{d\mid a}\varphi(d)=n$。

3. 将 $f(n)=\varphi(n)$ 和 $g(n)=n$ 代入 $F_k(n)$ 并化简：

$$F_k(n) = \begin{cases} \varphi(n) & k=1 \\ F_{k-1}(n) & k>1,k\bmod 2=0 \\ \varphi(F_{k-1}(n)) & k>1,k\bmod 2=1 \end{cases}$$

4. 将 $F_k(n)$ 打表：

$F_k(n)$	$F_1(n)$	$F_2(n)$	$F_3(n)$	$F_4(n)$	$F_5(n)$	$F_6(n)$	$F_7(n)$	$F_8(n)$
实际函数	$\varphi(n)$	$\varphi(n)$	$\varphi(\varphi(n))$	$\varphi(\varphi(n))$	$\varphi(\varphi(\varphi(n)))$	$\varphi(\varphi(\varphi(n)))$	$\varphi(\varphi(\varphi(\varphi(n))))$	$\varphi(\varphi(\varphi(\varphi(n))))$
嵌套次数	$1$	$1$	$2$	$2$	$3$	$3$	$4$	$4$

5. 不难发现，$F_k(n)$ 就是对 $n$ 嵌套 $\left\lfloor \frac{k+1}{2} \right\rfloor$ 次 $\varphi(n)$。

6. 由于经过若干次嵌套后会一直重复 $\varphi(1)=1$，所以当 $n$ 变为 $1$ 后可以跳过后面的嵌套，实际嵌套次数为 $O(\log{n})$ 级别。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=200005;
ll phi(ll n)
{
    ll res=n;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0) 
        {
            res=res/i*(i-1);
            while(n%i==0)n/=i;
    	}
    }
    if(n>1)res=res/n*(n-1);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k;
    cin>>n>>k;
    k=(k+1)/2;
    while(k--&&n>1)n=phi(n);
    cout<<n%mod<<'\n';
    return 0;
}