題解 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[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;//程式拜拜。
}