BZOJ3643 Phi的反函數（數論+搜尋）

題意：

輸入n<2^31，求使得phi(x)==n的最小x，無解輸出-1

設 x = p1^a1 * p2^a2 * …* pm^am (m<=10,pi為素數)

則 n == phi(x) == x * (p1-1)*p1 * (p2-1)*p2 * …* (pm-1)*pm

     == p1^(a1-1) * (p1-1) * p2^(a2-1) * (p2-1) * …* pm^(am-1) * (pm-1)

可以發現：(p1-1)*(p2-1)* …*(pm-1) 為n的因數 

又因為m不會超過10，是以在[2,sqrt(n)]内搜尋pi即可，若存在px>sqrt(n)，那麼這樣的x一定隻有一個，且ax==1，需要特殊判斷 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INF 2147483648ll
typedef long long LL;
int pri[100005],hash[100005];
LL ans=INF,pro=1;
int count=0,N;
LL min(LL a,LL b)
{
	if(a<b) return a;
	return b;
}
int is_prime(int x)
{
	int i,sq=(int)sqrt(x);
	for(i=1;pri[i]<=sq;i++)
		if(x%pri[i]==0) return 0;
	return 1;
}
void dfs(int t,int k)
{
	int i,j,tpro=pro,tt=t;
	if(pro>=ans) return;
	if(t==1)
	{
		ans=pro;
		return;
	}
	if( t>N && is_prime(t+1)==1 ) ans=min(ans,pro*(LL)(t+1));
	if( pri[k]-1>N || t<pri[k]-1 ) return;
	for(i=k;pri[i]<=N+1;i++)
	{
		if(pri[i]-1>t) return;
		if(t%(pri[i]-1)==0)
		{
			t/=(pri[i]-1);
			pro*=(LL)pri[i];
			dfs(t,i+1);
			while(t%pri[i]==0)
			{
				t/=pri[i];
				pro*=(LL)pri[i];
				dfs(t,i+1);
			}
			pro=tpro;
			t=tt;
		}
	}
}
int main()
{
	int n,i,j;
	scanf("%d",&n);
	N=(int)sqrt(n);
	for(i=2;i<=100000;i++)
		if(hash[i]==0)
		{
			pri[++count]=i;
			for(j=i;j<=100000;j+=i)
				hash[j]=1;
		}
	dfs(n,1);
	if(ans==INF) printf("-1");
	else printf("%lld",ans);
	return 0;
}