题解 P2350 【[HAOI2012]外星人】

· · 题解

不得不说这题的题面真的……晦涩艰深……

大致解释一下

\varphi^x(N) = 1

表示每次让N=\varphi(N)，重复 x 次的结果等于1

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

（就是题目最下方给的那公式然而它炸了）

看上去很复杂，不过结合题目中的\prod_{i = 1}^m p_i^{q_i}为N的标准分解形式这句话，上面展开就是：把N质因数分解成p_1^{q_1} p_2^{q_2} …… p_m^{q_m}，则$\varphi(N)=(p_1-1)p_1^{q_1-1}......(p_m-1)*p_m^{q_m-1}$

然后输入我也说下吧（因为我一开始连输入的是什么都没看懂）：出题人良心发现帮你把N质因数分解好了，输入的m，p，q意义就是上面的那些。

突然发现这篇题解最难打字的地方居然是翻译题目……

下面终于开始说到做法了

把那些公式说成人话，其实每次就是把N的每种质因子各取一个拿出来减一再乘回去（可能有点绕，原谅我这么烂的语文水平）

那么，想让N变成1，就要把N的质因子不断地减小，拆分成更多的质因子，以此类推，显然每个大于2的质因子都会经历分成不少于一个的2再变成1的过程。又因为每种质因子是同时减少的，所以若N为偶数则分出的2的个数就是总操作数（显然最后一步是2变成1，而每次最多只有一个2变成1），如果N为奇数那么第一步没有2变成1，要往后顺延一步，总操作数要加一。

（注：此处【分出的2的个数】指一个数减一后质因数分解，再将其中大于2的数重复此步骤最后剩下2的个数）

质因子最大不超过十万，因此可以DP预处理出每个质因子一共会分出多少个2：（设i分出2的个数为f[i]）

①f[p]=f[p-1] (p为质数)

p无法质因数分解，直接减一

②f[a*b]=f[a]+f[b]

仍没什么好解释的，假想a*b中先分a再分b就行了

剩下的就看注释吧，虽然说了这么多，不过代码倒是很短

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define LL long long
using namespace std;
const int N=3e4+1,M=1e5+10;
int t,c,m;bool isp[M];
LL a[N],b[N],ans,p[N],f[M];
int main(){
    scanf("%d",&t),f[1]=1;
    for(LL i=2;i<M;++i){
        if(!isp[i])p[++c]=i,f[i]=f[i-1];
        for(int j=1;j<=c&&p[j]*i<M;++j){
            isp[p[j]*i]=1,f[p[j]*i]=f[p[j]]+f[i];
            if(i%p[j]==0)break;
        }
    }//线性筛中求出f数组
    while(t--){
        scanf("%d",&m),ans=1;
        for(int i=1;i<=m;++i)
            scanf("%lld%lld",&a[i],&b[i]),
            ans+=((a[i]&1ll)?0:-1)+f[a[i]]*b[i];
            //上面已说了奇数结果要加一，因此先将ans赋值为1然后如果有偶数质因子（只有一个2）再减一
        printf("%lld\n",ans);
    }
    return 0;
}

题外话：整整六个月没写题解了（上次2.19）……第一次用这么多Markdown/LaTex，大佬勿喷