自动搬运

查看原文

来自洛谷，原作者为

	宁_缺 毕竟几人真得鹿，不知终日梦为鱼。

搬运于2025-08-24 21:36:40，当前版本为作者最后更新于2020-07-19 23:53:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

大致解释一下

$$\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，大佬勿喷