$$\Large\texttt{My Blog}$$


Description

题目链接:Luogu 2350

艾利欧在她的被子上发现了一个数字 $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

#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;
}