P4780-Phi的反函数【dfs】 正题

题目链接:https://www.luogu.com.cn/problem/P4780

题目大意

给出(n)，求一个最小的(x)满足(varphi(x)=n)。
若不存在或者大于(2^{31})则输出(-1)。

(1leq nleq 2^{31})

解题思路

考虑用(varphi)比较常用的公式，把(n)拆成若干个(prod (p_i-1)*p_i^{c_i})的形式。因为这个不会超过(log)个所以可以暴力搜索比较小的质数，然后直到(n)剩下一个(p_i+1)时或(1)时再暴力判断。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const ll N=46360;
ll n,ans,cnt,pri[N/10];
bool v[N];
void Prime(){
	for(ll i=2;i<N;i++){
		if(!v[i])v[i]=1,pri[++cnt]=i;
		for(ll j=1;j<=cnt&&i*pri[j]<N;j++){
			v[i*pri[j]]=1;
			if(i%pri[j]==0)break; 
		}
	}
	return;
}
bool IsPri(ll x){
	if(x%2==0)return 0;
	for(ll i=3;i*i<=x;i+=2)
		if(x%i==0)return 0;
	return 1;
}
void dfs(ll phi,ll x,ll k){
	if(phi>(1ll<<31))return;
	if(x==1){
		ans=min(ans,phi);
		return;
	}
	if(x>sqrt(n)&&IsPri(x+1))
		ans=min(ans,phi*(x+1));
	if(pri[k]>x)return;
	for(ll i=k;i<=cnt;i++){
		if(x%(pri[i]-1)==0){
			ll z=x/(pri[i]-1),p=phi*pri[i];
			dfs(p,z,i+1); 
			while(z%pri[i]==0){
				p*=pri[i];z/=pri[i];
				dfs(p,z,i+1);
			}
		}
	}
	return;
}
signed main()
{
	scanf("%lld",&n);
	Prime();ans=(1ll<<32);
	dfs(1,n,1);
	if(ans==(1ll<<32))puts("-1");
	else printf("%lld
",ans);
	return 0;
}