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