Skip to main content

CF776E The Holmes Children

· 3 min read
lailai
Student & Developer

解题思路

化简 f(n)f(n)

f(n)=i=1n1[gcd(i,ni)=1]=i=1n1[gcd(i,n)=1]=i=1n[gcd(i,n)=1]=φ(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)=φ(n)f(n)=\varphi(n) 就是欧拉函数,而 g(n)g(n)φ(n)\varphi(n) 的和函数,即 id(n)=nid(n)=n

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

证明:nn 个分数 1n,2n,,nn\frac{1}{n},\frac{2}{n},\dots,\frac{n}{n} 互不相等。考虑化简这些分数,得到新的 nn 个分数,他们的分母和分子互质,形如 ad,da\frac{a}{d},d\mid aaadd 互质。在所有 nn 个分数中,分母为 dd 的分数有 φ(d)\varphi(d) 个。所有不同分母的分数,其总数为 daφ(d)=n\sum_{d\mid a}\varphi(d)=n

f(n)=φ(n)f(n)=\varphi(n)g(n)=ng(n)=n 代入 Fk(n)F_k(n) 并化简:

Fk(n)={φ(n)k=1Fk1(n)k>1,kmod2=0φ(Fk1(n))k>1,kmod2=1F_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}

Fk(n)F_k(n) 打表:

Fk(n)F_k(n)实际函数嵌套次数
F1(n)F_1(n)φ(n)\varphi(n)11
F2(n)F_2(n)φ(n)\varphi(n)11
F3(n)F_3(n)φ(φ(n))\varphi(\varphi(n))22
F4(n)F_4(n)φ(φ(n))\varphi(\varphi(n))22
F5(n)F_5(n)φ(φ(φ(n)))\varphi(\varphi(\varphi(n)))33
F6(n)F_6(n)φ(φ(φ(n)))\varphi(\varphi(\varphi(n)))33
F7(n)F_7(n)φ(φ(φ(φ(n))))\varphi(\varphi(\varphi(\varphi(n))))44
F8(n)F_8(n)φ(φ(φ(φ(n))))\varphi(\varphi(\varphi(\varphi(n))))44

不难发现,Fk(n)F_k(n) 就是对 nn 嵌套 k+12\left\lfloor \frac{k+1}{2} \right\rfloorφ(n)\varphi(n)

经过若干次嵌套后会重复 φ(1)=1\varphi(1)=1,所以当 nn 变为 11 后可以跳过后面的嵌套,实际嵌套次数为 O(logn)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;
}