题解 P2350 【[HAOI2012]外星人】-阿里云开发者社区

开发者社区> 人工智能> 正文

题解 P2350 【[HAOI2012]外星人】

简介: 题目链接 还是本宝宝写题解的一贯习惯 $ :$ 先吐槽吐槽这道题$……$相信不少同学第一眼一定没有看懂题。(因为我也没看懂)~~初中~~数学知识:对于函数 $ f(x)$ 有 $f^{-1}(x)$ 为该函数的反函数。

题目链接

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

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

~~初中~~数学知识:

对于函数 $ 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[100010];//欧拉函数值
bool ins[100010];//标记有没有被筛过
int prime[100010];//记录质数
int cnt;//质数个数
inline void init(){
    pni[1]=1;
    for(int i=2;i<=100000;i++){
        if(!ins[i]) prime[++cnt]=i,pni[i]=pni[i-1];
        for(int j=1;j<=cnt&&prime[j]*i<=100000;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=1;
int p;int q;
signed main()
{
    init();
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&p,&q);
            if(p==2) ans--;
            ans+=pni[p]*q;//统计答案
        }
        printf("%lld\n",ans);
        ans=1;
    }
    return 0;//程序拜拜。
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章