洛谷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;
}