[HAOI2012]外星人

题意

给一个数N，求它经过多少次取\(phi\)可以变成1

思路

由于只有\(\varphi_{1}\)和\(\varphi_{2}\)为1，所以原数变成1的过程必经2，由

\[\varphi(\prod_{i = 1}^m p_i^{q_i}) = \prod_{i = 1}^m (p_i - 1)*p_i^{q_i-1}\]

可知一次操作只能消掉一个2，所以可以通过求出2的个数来求操作次数

设\(f_i\)表示\(i\)变成1的过程中会生成的2的个数，有以下性质：

\(i\)为质数时，\(f_i=f_{i-1}\)，即质数\(i\)和\(i-1\)生成的2个数相同

\(i\)不为质数时，\(f_i=f_a*f_b ,(a*b=i)\)，即两数互不干扰，这里利用这个性质将原数质因数分解即可

对于\(n=\prod{p_{i}^{q_{i}}}\)，有\(ans=\prod{f_{p_i}*q_i}\)

之所以用2的个数表示答案，是因为假设一次操作消一个2，但如果一开始\(n\)没有2，就需要额外的一步来生成2

Code

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int T,n;
int p[N],isnotp[N],cnt;
ll f[N];

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void init(int maxn)
{
    f[1]=1;
    isnotp[1]=1;
    for(int i=2;i<=maxn;++i)
    {
        if(!isnotp[i]) p[++cnt]=i,f[i]=f[i-1];
        for(int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
        {
            isnotp[p[j]*i]=1;
            f[p[j]*i]=f[p[j]]+f[i];
            if(i%p[j]==0) break;
        }
    }
}
int main()
{
    init(N-5);
    read(T);
    while(T--)
    {
        read(n);
        ll ans=0,flag=1;
        for(int i=1;i<=n;++i)
        {
            int p,c;
            read(p);read(c);
            if(p==2) flag=0;
            ans+=f[p]*c;
        }
        printf("%lld\n",ans+flag);
    }
    return 0;
}

[HAOI2012]外星人

原文：https://www.cnblogs.com/Chtholly/p/11679609.html