「HAOI 2012」外星人

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

Description

题目链接：BZOJ 2749

艾利欧在她的被子上发现了一个数字 $n$，她觉得只要找出最小的 $x$ 使得，$\varphi^x(n)=1$。根据这个 $x$ 她就能找到曾经绑架她的外星人的线索了。现在她给你这个数字 $n$ 的标准分解形式 $n=\prod_{i=1}^m {p_i}^{q_i}$，请你帮助她算出最小的 $x$。

本题 $T$ 组数据。

数据范围：$1\le T\le 50$，$1\le p_i\le 10^5$，$1\le q_i\le 10^9$

Solution

读完题目之后一脸懵逼：求 $\varphi(n)$ 的 $x$ 阶导数？？？

其实这题的题意是：给定 $n$，每次使 $n$ 等于 $\varphi(n)$，求最少几次操作后 $n=1$。

首先可以打表发现如下规律：只有 $1$ 和 $2$ 的 $\varphi$ 值才是 $1$！

接下来我们根据 $\varphi(n)$ 的定义，有如下式子：

那么意味着每次操作会把上一次操作的答案中的最多一个 $2$ 变为 $1$（注意：不可能同时变化多个 $2$）。

所以我们只要求出每个质因子在操作过程中会产生多少个 $2$ 即可。

具体的过程为：我们设 $f(i)$ 表示 $i$ 在操作过程中会产生多少个 $2$；那么有如下转移方程：

  1. 当 $i$ 为质数时，$f(i)=f(i-1)$，因为质数进行操作后变为 $i-1$ 而没有增加 $2$ 的个数，因此应该和 $f(i-1)$ 的答案相等。
  2. 当 $i=a\times b$ 时，$f(i)=f(a)+f(b)$ 因为 $i$ 可以表示为两个数相乘，那么其 $2$ 的次数应该为两者之和。

但是！我们发现直接这样写是会错的！考虑如下情况：

  • 原数为 $3$，那么我们第一次操作不会把任何一个 $2$ 改为 $1$（因为 $3$ 中本来就没有任何一个因子 $2$）。所以需要 $2$ 次操作而不是 $3$ 次！

因此我们需要处理一下细节问题：当原数中没有因子 $2$ 时，答案 $+1$。

时间复杂度：$O(p_i+Tn)$

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
 
#include <cstdio>

const int N=1e5+5;
int n,tot,p[N],f[N];
bool flg[N];

void sieve(int n) {
    f[1]=1;
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i,f[i]=f[i-1];
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1,f[i*p[j]]=f[i]+f[p[j]];
            if(i%p[j]==0) break;
        }
    }
}
int main() {
    sieve(N-5);
    int T;
    for(scanf("%d",&T);T--;) {
        scanf("%d",&n);
        long long ans=0,flg=0;
        for(int i=1;i<=n;++i) {
            int p,c;
            scanf("%d%d",&p,&c);
            if(p==2) flg=1;
            ans+=1LL*f[p]*c;
        }
        if(!flg) ++ans;
        printf("%lld\n",ans);
    }
    return 0;
}
0%