手机网站生成app,网页设计图片滑动代码,去香洲会变黄码吗,wordpress 如何进入数据库正题
题目链接:https://www.luogu.com.cn/problem/P4780 题目大意
给出nnn#xff0c;求一个最小的xxx满足φ(x)n\varphi(x)nφ(x)n。 若不存在或者大于2312^{31}231则输出−1-1−1。 1≤n≤2311\leq n\leq 2^{31}1≤n≤231 解题思路
考虑用φ\varphiφ比较常用的公式…正题
题目链接:https://www.luogu.com.cn/problem/P4780 题目大意
给出nnn求一个最小的xxx满足φ(x)n\varphi(x)nφ(x)n。 若不存在或者大于2312^{31}231则输出−1-1−1。
1≤n≤2311\leq n\leq 2^{31}1≤n≤231 解题思路
考虑用φ\varphiφ比较常用的公式把nnn拆成若干个∏(pi−1)∗pici\prod (p_i-1)*p_i^{c_i}∏(pi−1)∗pici的形式。因为这个不会超过logloglog个所以可以暴力搜索比较小的质数然后直到nnn剩下一个pi1p_i1pi1时或111时再暴力判断。 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long long
using namespace std;
const ll N46360;
ll n,ans,cnt,pri[N/10];
bool v[N];
void Prime(){for(ll i2;iN;i){if(!v[i])v[i]1,pri[cnt]i;for(ll j1;jcnti*pri[j]N;j){v[i*pri[j]]1;if(i%pri[j]0)break; }}return;
}
bool IsPri(ll x){if(x%20)return 0;for(ll i3;i*ix;i2)if(x%i0)return 0;return 1;
}
void dfs(ll phi,ll x,ll k){if(phi(1ll31))return;if(x1){ansmin(ans,phi);return;}if(xsqrt(n)IsPri(x1))ansmin(ans,phi*(x1));if(pri[k]x)return;for(ll ik;icnt;i){if(x%(pri[i]-1)0){ll zx/(pri[i]-1),pphi*pri[i];dfs(p,z,i1); while(z%pri[i]0){p*pri[i];z/pri[i];dfs(p,z,i1);}}}return;
}
signed main()
{scanf(%lld,n);Prime();ans(1ll32);dfs(1,n,1);if(ans(1ll32))puts(-1);else printf(%lld\n,ans);return 0;
}
