题解 P4780 【Phi的反函数】

编者注：该题解已被 LHQing hack

hack in:20 out:33 ans:25

一道较为简单的搜索题。

设$s$为$x$的质因子的个数，则$\phi (x)=x\times \prod _{i=1}^s{\displaystyle \frac{p_i-1}{p_i}}=n$.

由上式可得，如果要从$n$反推最小的$x$，则需要保证$n$的分解式没有重复项，且每一项+1一定是质数（否则一定可以用更小的几个质数代替该项）。

因此可以有以下剪枝：

• 枚举$x$的因数时保证单调性。

• 对每一种因数$d$，判断$d+1$是否为质数。

• 最优性剪枝。

经过以上剪枝后，运行时间即可保持在5ms以内。

（本代码时间18ms，代码长度612B。最优解rk4，并且应该是所有AC代码中最短的。）

#include <cstdio>
#define int unsigned//防炸int
signed stk[100010]={-1};//第一项无论如何也得过
int n,ans=1,minn=3e9;
bool isprime(int x){
	if(x==2||x==3) return 1;
	if(x%6!=1&&x%6!=5) return 0;//判断质数小优化
	for(int i=2;i*i<=x;i++)
		if(x%i==0) return 0;
	return 1;
}
void dfs(int now,int x,int tmp){
	if(tmp>=minn) return;//最优性剪枝
	if(x==1) {minn=tmp;return;}
	if(isprime(x+1)) dfs(now+1,1,tmp*(x+1));//当x为质数时需特判
	for(signed i=2;i*i<=x;i++)
		if(x%i==0&&i>stk[now-1]&&isprime(i+1)){//保证单调性+提前判断质数
			stk[now]=i;
			dfs(now+1,x/i,tmp*(i+1));
		}
}
signed main(){
	scanf("%u",&n);
	dfs(1,n,1);
	if(minn>(1u<<31)) puts("-1");//防炸int
	else printf("%u",minn);
	return 0;
}