洛谷P2350 [HAOI2012]外星人 题解

题目链接：P2350 [HAOI2012]外星人

题意：

多组数据

给出正整数 $N$ 的标准分解形式 $\prod_{i=1}^{m}p_i^{q_i}$

求最小的正整数 $x$ 使得 $\varphi^{x}(N) = 1$

注意到

$$\varphi\left(\prod\limits_{i=1}^{m}p_i^{q_i}\right) = \prod_{i=1}^{m}(p_i-1)\times p_i^{q_i-1}$$

对于含质因子 $2$ 的数，迭代一次会消去一个 $2$

对于不含质因子 $2$ 的数，迭代一次会产生至少一个 $2$

不难发现，答案与产生的 $2$ 的个数有关

则对于所有含质因子 $2$ 的 $N$ 答案即为迭代产生的所有的 $2$ 的个数

否则答案就是额外迭代一次后，再重复迭代产生的所有的 $2$ 的个数

设 $f(n)$ 为 $n$ 在迭代过程中产生的 $2$ 的个数 $\left(n=\sum_{i=1}^{s}p_i^{q_i}\right)$

当 $n$ 为素数时，有

$$f(n)=f(n-1)$$

当 $n$ 为合数时，有

$$f(n)=\sum_{i=1}^{s} q_i f(p_i)$$

这个东西可以用筛法去更新答案，预处理即可

时间复杂度 $O(\max(p))$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
int n;
int f[N],prime[N],ck[N],pcnt;
void Euler()
{
    ck[1]=1;f[1]=1;
    for(int i=2; i<=N; i++)
    {
        if(!ck[i])
        {
            prime[++pcnt]=i;
            f[i]=f[i-1];
        }
        for(int j=1; j<=pcnt&&i*prime[j]<=N; j++)
        {
            int pos=i*prime[j];
            ck[pos]=1;f[pos]=f[i]+f[prime[j]];
            if(i%prime[j]==0)break;
        }
    }
}
void solve()
{
    // clear();
    int res=0,flag=1;
    cin >> n;
    for(int i=1,p,q; i<=n; i++)
    {
        cin >> p >> q;
        if(p==2)flag=0;
        res+=f[p]*q;
    }
    cout << res+flag << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int _Q=1;cin >> _Q;
    Euler();
    while(_Q--)solve();
    return 0;
}