还是本宝宝写题解的一贯习惯 $ :$ 先吐槽吐槽这道题$……$
相信不少同学第一眼一定没有看懂题。（因为我也没看懂）
~~初中~~数学知识：
对于函数 $ 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;//程序拜拜。 }
