题解：CF776E The Holmes Children

wusixuan · 2025-07-15 15:38:51 · 题解

这道题就是究极无敌诈骗题，实际上看懂了非常简单。

考虑 f 是什么。因为 \gcd(a,b)=1 和 \gcd(a,a+b)=1 等价（这个是很通用的一个结论，不知道的自己证明一下充要性），所以 \gcd(i,n-i)=1 和 \gcd(i,n)=1 等价，然后你会发现 f 是什么？

f(n)=\sum_{i=1}^{n-1}[\gcd(i,n)=1]\\ f(n)=\varphi(n)

原来 f 是这么熟悉的一个东西，不禁让人唏嘘。

考虑 g 是什么。不难发现这个式子可以表现成一个卷积的形式：

g=1*f=1*\varphi=\text{id}

所以 g(i)=i，又是一个很熟悉的东西，这个时候已经诈骗到了极点。

所以：

k=1$ 时，$F_k(n)=\varphi(n)
k$ 为偶数时，$F_k(n)=F_{k-1}(n)
k$ 为奇数时，$F_k(n)=\varphi(F_{k-1}(n))=\varphi(F_{k-2}(n))

所以这就变成了给定 n,k，叫你每一次 \varphi(n) \to n，一共执行 \lfloor \frac{k+1}{2}\rfloor 次。

但是 k 很大，所以考虑发掘 \varphi 函数的性质：

所以 \varphi(n)\to n 的次数不可能超过 O(\log n) 次，直接暴力执行即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
bool f[N];
int p[N], n, k;

void get() {
    f[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!f[i])
            p[++p[0]] = i;
        for (int j = 1; j <= p[0] && i * p[j] < N; j++) {
            f[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}

int phi(int x) {
    int ans = x;
    for (int i = 1; i <= p[0] && p[i]*p[i] <= x; i++) {
        if (x % p[i])
            continue;
        ans = ans / p[i] * (p[i] - 1);
        while (x % p[i] == 0)
            x /= p[i];
    }
    if (x > 1)
        ans = ans / x * (x - 1);
    return ans;
}

signed main() {
    get();
    cin >> n >> k;
    for (int i = 1; i <= (k + 1) / 2 && n > 1; i++)
        n = phi(n);
    cout << n % 1000000007 << endl;
    return 0;
}