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

场上想了个自认为是错解的想法，$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;
}