正题

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

---

题目大意

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

$1\le n\le 2^{31}$

---

解题思路

考虑用$\phi$比较常用的公式，把$n$拆成若干个$\prod (p_i-1)\ast 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\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的P4780-Phi的反函数【dfs】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。