解法不再多说，主要讲实现。

实际上，我们发现，$p-1$ 会使所有它的质因数的幂次 $+1$，而一个数的质因数至多有 $\log p$ 个，所以我们可以预处理出所有数的最小质因数，然后倒着扫一遍，不需要建图。

时间复杂度 $O(\sum(\max_{i=1}^{n}{p_i}+n\log p))$，显然可以通过。

代码：

#include<bits/stdc++.h>
using namespace std;
bool pri[100005];
int mi[100005];
int len[100005];
long long ji[100005];
int main(){
	pri[1]=1;
	for(int i=2;i<=100000;i++){
		if(!pri[i]){
			mi[i]=i;
			for(int j=i*2;j<=100000;j+=i){
				if(!pri[j]){
					mi[j]=i;
				}
				pri[j]=1;
			}
		}
	}
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		ji[2]=0;
		for(int i=1;i<=n;i++){
			int p,q;
			cin>>p>>q;
			ji[p]+=q;
		}
		bool flag=ji[2]==0;
		for(int i=100000;i>=3;i--){
			if(ji[i]){
				int l=i-1;
				while(l>1){
					ji[mi[l]]+=ji[i];
					l/=mi[l];
				}
				ji[i]=0;
			}
		}
		cout<<ji[2]+flag<<"\n";
	}
	return 0;
}

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

大致解释一下

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

什么是欧拉函数？哦有提示啊。

场上想了个自认为是错解的想法，$20$ 分钟写完结果过了。后面才证明是对的。

首先一次 $\phi (p^q)$ 会让 $p$ 的幂次减一，$p-1$ 的幂次加一。

但是学过一点点数学的人都知道，这个提示部分的所有 $p_i$ 都得是质数。所以我们还需要对 $p-1$ 进行质因数分解。

然后我们将 $p$ 同分解后的 $p-1$ 的各项质因子连一条边权为这个质因子在 $p-1$ 中的幂次的边。这样我们就得到了一个 DAG。

定义一个数对应的点的权值为这个数当前的幂次。

那么每次操作相当于将每一个权值大于 $1$ 的节点的权值减一，然后将他连向的每一条边的对应节点的权值加上对应的边权。

注意到整个 DAG 出度为 $0$ 的点只有 $2$ 一个。

到这里我就开始怀疑我代码的正确性。因为我以为会出现暂时断流的情况，事实证明并不会，因为每一个质因子都会向 $2$ 连一条边。

问题转化成 $N$ 能产生多少个 $2$。

我们直接逆向预处理每个质数 $p_i$ 每有一个能产生多少个 $2$。这个可以拓扑。

然后再判断一下初始有没有 $2$ 就行了。

时间复杂度是个玄学的问题，不过不会爆。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,inf=1e9;
int p[N],v[N],pr,dp[N],rd[N];map<int,int>mp;
vector<pair<int,int>>G[N];
void init()
{
	pr=0;memset(v,0,sizeof(v));
	for(int i=2;i<=N-10;i++)
	{
		if(!v[i])p[++pr]=i,mp[i]=pr;
		for(int j=1;(j<=pr)&&(i*p[j]<=N-10);j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	for(int i=1;i<=pr;i++)
	{
		int p1=p[i]-1;
		for(int j=1;j<i&&p1!=1;j++)if(p1%p[j]==0)
		{
			int sum1=0;
			while(p1%p[j]==0)p1/=p[j],sum1++;
			G[j].push_back({i,sum1}),rd[i]++;
		}
	}
	deque<int>q;
	for(int i=1;i<=pr;i++)if(rd[i]==0)q.push_back(i),dp[i]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(auto i:G[x])
		{
			int y=i.first,w=i.second;
			dp[y]+=dp[x]*w;
			rd[y]--;if(rd[y]==0)q.push_back(y);
		}
	}
}
void solve()
{
	int n,bk=1,ans2=0;cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;cin>>x>>y;
		if(x==2)bk=0;
		ans2+=dp[mp[x]]*y;
	}
	cout<<bk+ans2<<'\n';
}
signed main()
{
	init();
	int t;cin>>t;
	while(t--)solve();
	return 0;
}