rt，加了一个特别强的优化。

具体来说，我们用 pr 求出 $\gcd(x,\dfrac{z}{x})$ 的所有质因数，然后通过 dfs 决定每个质因数选多少个来求出所有可能的$y$。

此时，我加的优化是：设 $z$ 有 $zp[p]$ 个质因子 $p$，$x$ 有 $xp[p]$ 个质因子 $p$，则设 $y$ 对于质因子 $p$ 放 $i$ 个当且仅当 $xp[p]+i+\min(xp[p],i)<=zp[p]$。这是一个很强的优化，加上就过了。

dfs 处的代码：

void dfs(int wz,int now)
{
	int g=gcd(z/x/now,x);
	if(g==now)
	{
		ans=min(ans,z/x/now);
		return;
	}
	if(wz==cnt+1 || g>z/x/now) return;
	int nnow=now;
	for(int i=0; xp[wz]+i+(xp[wz]<i?xp[wz]:i)<=zp[wz]; ++i)
	{
		dfs(wz+1,nnow);
		nnow*=pri[wz];
	}
}

AC 记录

所以这种做法可以被卡掉吗 :)