题解 P2350 【[HAOI2012]外星人】

题目链接

还是本宝宝写题解的一贯习惯 $ :$ 先吐槽吐槽这道题$……$

相信不少同学第一眼一定没有看懂题。（因为我也没看懂）

~~初中~~数学知识：

对于函数 $ f(x)$ 有 $f^{-1}(x)$ 为该函数的反函数。

而当 $ n∈N^{*} $ 时， $f^{n}(x)$ 表示$f(x)$ 的 $n$阶导数。

于是本宝宝看到这题后~~一脸懵逼~~炸了：

喵 $ ?$ $ $ $ !$ 出题人您来告诉我欧拉函数怎么求导$ !$ $ $ $ !$ $ $ $ !$

看一眼题解，才知道$……$

我的数学白学了$?!!$

---

转入正题 $:$

其实，给定 $n$ ，让你求 $x$ 使得

$$\varphi^{x}(N)=1$$

的意思其实是：

每次取 $N=\varphi(N)$ 问至少操作几次后使得 $N=1$

也就是说$:$

$$\varphi(\varphi(…\varphi(N)))=1$$

的最少取 $\varphi$ 的次数即为$ x $

---

好了我们终于理解完题意了。

现在我们可以开始做题了。

这里要引用一句~~名言~~:

如果你是一个在省选考场即将$AK$的人，闲来无事，打了一个 $\varphi(1)-\varphi(1000000)$的表。

然后你惊奇的发现，只有当 $ n$ $=$ $1,2$ 时欧拉函数值是 $0$

然后这玩意要是 $ 1$ 的话，答案显然。

其余的，就根据

$$\varphi(\prod_{i=1}^{m}p_{i}^{q_{i}})=\prod^{m}_{i=1}(p_{i}-1)*p_{i}^{q_{i}-1}$$

所以，每次操作会将上一次操作的答案中的一个因子$2$变为$1$

所以，求操作过程中会产生多少个因子$2$就好了。

---
下面来讨论特例：

$1.$ 对于 $ 2^{n}$ $,$ 我们的操作次数是 $n$ $,$ 显然是这样的。

$2.$ 对于一开始是一个质数，我们第一次操作不会将其中的一个因子$2$变为$1$，所以，这时候 $ans++$

---

好了，上代码：

// luogu-judger-enable-o2

#include<iostream>

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

#define int long long//个人习惯

int pni[];//欧拉函数值

bool ins[];//标记有没有被筛过

int prime[];//记录质数

int cnt;//质数个数

inline void init(){

    pni[]=;

    for(int i=;i<=;i++){

        if(!ins[i]) prime[++cnt]=i,pni[i]=pni[i-];

        for(int j=;j<=cnt&&prime[j]*i<=;j++)

        {

            ins[prime[j]*i]=true;

            pni[prime[j]*i]=pni[prime[j]]+pni[i];

            if(!(i%prime[j])) break;

        }

    }

    return ;

}

//以上是欧拉线性筛的模板。

int t;

int n;int ans=;

int p;int q;

signed main()

{

    init();

    scanf("%lld",&t);

    while(t--)

    {

        scanf("%lld",&n);

        for(int i=;i<=n;i++){

            scanf("%lld%lld",&p,&q);

            if(p==) ans--;

            ans+=pni[p]*q;//统计答案

        }

        printf("%lld\n",ans);

        ans=;

    }

    return ;//程序拜拜。

}

巴特西

题解 P2350 【[HAOI2012]外星人】

最新文章

热门文章