「Codeforces 776E」The Holmes Children

发表于 | | 阅读次数:
字数统计: 625 字

Description

题目链接：Codeforces 776E

Holmes 的孩子们在争论谁才是他们中最聪明的。

Mycroft 提出了如下的函数求值问题：已知 $f(1)=1​$，且当 $n\ge 2​$ 时，$f(n)​$ 表示满足 $x+y=n​$ 的互质的正整数对 $(x,y)​$ 的对数，$g(n)=\sum_{d\mid n}f\left(\frac{n}{d}\right)​$。

她定义了一个函数 $F_k(n)$，其值可以通过如下式子递归求解：

现在她希望你对于给定 $n,k$，求出 $F_k(n)\bmod 1000000007$ 的值。

数据范围：$1\le n,k\le 10^{12}$

Solution

我们先推导一下 $f(n)$ 和 $g(n)$ 函数到底长成什么样子：

由于 $f(n)$ 就是 $\varphi(n)$ 函数，那么 $g(n)$ 函数可以通过如下式子表示：

显然这是一个卷积的形式：

因此 $g(n)=n$！

那么递归式变为：

我们可以找规律发现，$F_k(n)$ 的值就是对 $n$ 求 $\left\lfloor\frac{k+1}{2}\right\rfloor$ 次 $\varphi$ 函数。

显然我们不能真的求 $O(k)​$ 次 $\varphi​$，由于 $n​$ 求 $O(\log n)​$ 次 $\varphi​$ 的值就是 $1​$，此时再求 $\varphi​$ 就没有意义了。故我们只需要求 $\max\left(\log n,\left\lfloor\frac{k+1}{2}\right\rfloor\right)​$ 次 $\varphi​$ 即可。

时间复杂度：$O\left(\max\left(\log n,\left\lfloor\frac{k+1}{2}\right\rfloor\right)\sqrt n\right)​$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <cstdio>

const int N=1e6+5;
int tot,p[N];
bool flg[N];

void sieve(int n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
long long phi(long long x) {
    long long ans=x;
    for(int i=1;i<=tot&&1LL*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;
}
int main() {
    sieve(N-5);
    long long n,k;
    scanf("%lld%lld",&n,&k);
    k=(k+1)/2;
    for(long long i=1;i<=k&&n>1;++i) {
        n=phi(n);
    }
    printf("%lld\n",n%1000000007);
    return 0;
}
0%