题解 P2350 【[HAOI2012]外星人】

Siyuan

2019-02-08 11:00:51

Solution

[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-HAOI-2012-Extra-Terrestrial/) --- ## Description > 题目链接:[Luogu 2350](https://www.luogu.org/problemnew/show/P2350) 艾利欧在她的被子上发现了一个数字 $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)$ 的定义,有如下式子: $$\varphi\left(\prod_{i=1}^m {p_i}^{c_i}\right)=\prod_{i=1}^m (p_i-1)\times {p_i}^{c_i-1}$$ 那么意味着每次操作会把上一次操作的答案中的**最多一个 $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 ```cpp #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; } ```