化简 f(n):
f(n)=i=1∑n−1[gcd(i,n−i)=1]=i=1∑n−1[gcd(i,n)=1]=i=1∑n[gcd(i,n)=1]=φ(n)
f(n)=φ(n) 就是欧拉函数,而 g(n) 是 φ(n) 的和函数,即 id(n)=n:
g(n)=d∣n∑φ(d)=id(n)=n
证明:n 个分数 n1,n2,…,nn 互不相等。考虑化简这些分数,得到新的 n 个分数,他们的分母和分子互质,形如 da,d∣a 且 a 与 d 互质。在所有 n 个分数中,分母为 d 的分数有 φ(d) 个。所有不同分母的分数,其总数为 ∑d∣aφ(d)=n。
将 f(n)=φ(n) 和 g(n)=n 代入 Fk(n) 并化简:
Fk(n)=⎩⎨⎧φ(n)Fk−1(n)φ(Fk−1(n))k=1k>1,kmod2=0k>1,kmod2=1
将 Fk(n) 打表:
Fk(n) | 实际函数 | 嵌套次数 |
---|
F1(n) | φ(n) | 1 |
F2(n) | φ(n) | 1 |
F3(n) | φ(φ(n)) | 2 |
F4(n) | φ(φ(n)) | 2 |
F5(n) | φ(φ(φ(n))) | 3 |
F6(n) | φ(φ(φ(n))) | 3 |
F7(n) | φ(φ(φ(φ(n)))) | 4 |
F8(n) | φ(φ(φ(φ(n)))) | 4 |
不难发现,Fk(n) 就是对 n 嵌套 ⌊2k+1⌋ 次 φ(n)。
经过若干次嵌套后会重复 φ(1)=1,所以当 n 变为 1 后可以跳过后面的嵌套,实际嵌套次数为 O(logn) 级别。
#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;
}