专栏文章

题解：CF776E The Holmes Children

LLionBlaze
CF776E题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miorugsi
此快照首次捕获于
2025/12/03 00:07
3 个月前
此快照最后确认于
2025/12/03 00:07
3 个月前
查看原文
这题目前中文翻译疑似不太有素质，答案要对 109+7\bm{10^9+7} 取模。
容易发现 f(x)=φ(x)f(x)=\varphi(x)，也就是 [1,x][1,x] 中与 xx 互质的元素个数。
证明：
首先理解方括号 [P][P]。这是艾弗森括号，当 PP 为真时值为 11 否则为 00。
那么 gcd⁡(i,n−i)=1\gcd(i,n-i)=1 代表什么？我们有 gcd⁡(x,y)=gcd⁡(x,x−y)\gcd(x,y)=\gcd(x,x-y)，反用就得到了 gcd⁡(i,n−i)=gcd⁡(i,n)\gcd(i,n-i)=\gcd(i,n)。
所以是 ∑i=1n−1[gcd⁡(n,i)=1]\displaystyle\sum_{i=1}^{n-1} [\gcd(n,i)=1]。
而 nn 和 nn 必定不互质（因为 n≥2n \ge 2，n=1n=1 是显然成立的），所以把求和上界改为 nn 不会导致任何问题。
容易发现 g(n)=ng(n)=n。
证明：
φ\varphi 积性，不证。
一个数因子的积性函数和还是积性函数。所以 gg 是积性的。当 n=pkn=p^k 时因子有 1,p,p2,…,pk1,p,p^2,\dots,p^k，而 φ(pk)=(p−1)pk−1\varphi(p^k)=(p-1)p^{k-1}，φ(1)=1\varphi(1)=1，求和得到 1+(p−1)×pk−1p−1=pk1+(p-1)\times\dfrac{p^k-1}{p-1}=p^k，对于质数的幂证毕，所以对于所有的 nn 都成立。
其实这个有很多种证法。
所以我们得到：
Fk(n)={φ(n)k=1Fk−1(n)k>1,k≡0(mod2)φ(Fk−1(n))k>1,k≡1(mod2)F_k(n)=\begin{cases} \varphi(n)&k=1\\F_{k-1}(n)&k>1,k\equiv 0\pmod 2\\\varphi(F_{k-1}(n))&k>1,k\equiv 1\pmod 2\end{cases}
显然当 k≡1k\equiv 1 的时候可以直接减去 22。
从而可以得到，Fk(n)=φ(⌈k2⌉)(n)F_k(n)=\varphi^{\left(\left\lceil\frac{k}{2}\right\rceil\right)}(n)，其中 f(k)(x)f^{(k)}(x) 是函数迭代记号，也就是 f(f(f(…f(n)… )))f(f(f(\dots f(n)\dots)))，共有 kk 层。
计算 φ(n)\varphi(n) 有一种简单的方法，考虑其质因子分解，假设质数为 p1…pkp_1\dots p_k，而 φ(n)=n(1−1p1)(1−1p2)(1−1p3)…(1−1pk)\varphi(n)=n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\left(1-\dfrac{1}{p_3}\right)\dots \left(1-\dfrac{1}{p_k}\right)。
证明：
φ\varphi 积性。然后证毕。
可以在 O(n)\mathcal O(\sqrt{n}) 的时间复杂度之内计算出质因子分解，所以可以在相同的时间复杂度之内计算出 φ\varphi 函数值。
然而 kk 可能很大，我们的算法是 O(kn)\mathcal O(k\sqrt{n}) 的。
但是我们发现不停求 φ\varphi 很容易就变为 11 了。这时我们发现只要判断 n=1n=1 中途退出就能过。为什么？
当 nn 为奇数且 n>1n>1 时，我们有 φ(n)\varphi(n) 为偶数。我们把求 φ\varphi 的式子中 1−1pi1-\dfrac{1}{p_i} 转化为 pi−1pi\dfrac{p_i-1}{p_i}，显然一个数所有质因子的乘积是自身的因子，所以如果分母上是偶数则整个式子都是偶数。而 pip_i 如果为偶数则 nn 为偶数，矛盾。所以 φ(n)\varphi(n) 是偶数。
当 nn 为偶数时，φ(n)\varphi(n) 的后面一串乘积中有 (1−1p1)(1-\dfrac{1}{p_1})，而 p1=2p_1=2，所以 φ(n)≤n2\varphi(n)\le\dfrac{n}{2}（实际上当 n=2kn=2^k 时取等）。顺便可以证明 φ(n)\varphi(n) 为偶数（除非 n=2n=2。证法是如果 4∣n4\mid n 则显然。否则 nn 必然有非 22 质因子，仿照我们证明 nn 为奇数时的过程即可）。
所以显然迭代次数是 O(log⁡k)\mathcal O(\log k) 级别的。这样我们就放心了。作为娱乐，我们还可以干得更精确一些，可以得到：
  • 刚开始可能有一次迭代，把 nn 变为偶数。这个过程进行 ≤1\le 1 次。
  • 此后 nn 一直是偶数（除了最后 2→12\to 1），每次至少减半。这个过程进行 ≤log⁡2n\le \log_2 n 次。
最终会迭代最多 1+log⁡2n1+\log_2 n 次。
CPP
#include <cstdio>

using namespace std;

long long getphi(long long x)
{
    long long res = x;
    for(long long i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            while(x%i==0) x/=i;
            res = res / i * (i-1);
        }
    }
    if(x != 1) res = res / x * (x-1);
    return res;
}

int main()
{
    long long n, k;
    scanf("%lld%lld", &n, &k);
    k = (k+1)/2;
    while(k-- && n != 1)
    {
        n = getphi(n);
    }
    printf("%lld\n", n % 1000000007);
    return 0;
}
sub。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...