题解：CF776E The Holmes Children

· · 题解

解题思路

化简 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}

因此 f(n)=\varphi(n) 就是欧拉函数，而 g(n) 是 \varphi(n) 的和函数，即 \operatorname{id}(n)=n：

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

证明：考虑 n 个分数 \frac{1}{n},\frac{2}{n},\dots,\frac{n}{n}。将它们化为最简分数，得到 n 个新的分数 \frac{a}{d}，其中 d 是 n 的约数且 a 与 d 互质。显然分母为 d 的分数有 \varphi(d) 个。因此化简后的不同分数总数为 \sum_{d\mid n}\varphi(d)=n。

将 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}

将 F_k(n) 打表：

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

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

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

参考代码

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

using ll=long long;
const int mod=1e9+7;
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>>1;
    while(k--&&n>1)n=phi(n);
    cout<<n%mod<<'\n';
    return 0;
}