bzoj 3643 Phiの逆関数検索
異なる素因数は11個しかないので検索できます.xの1つの素因数uを列挙し、uは条件に合致し、(u−1)|nのみである.そしてxの>n^0.5の素因数を特判すればよい.
MACコードは以下の通りである.
by lych
2016.2.22
MACコードは以下の通りである.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define ll long long
using namespace std;
int n,m,cnt,c[100005]; bool vis[100005]; ll ans;
bool prm(int x){
int sz=(int)sqrt(x),i;
for (i=1; c[i]<=sz; i++) if (!(x%c[i])) return 0;
return 1;
}
void dfs(int k,int now,ll sum){
if (sum>=ans) return; int i;
if (now==1){ ans=sum; return; }
if (now>m && prm(now+1)) ans=min(ans,sum*(now+1));
for (i=k+1; c[i]-1<=m; i++){
if (c[i]-1>now) break;
if (!(now%(c[i]-1))){
int x=now/(c[i]-1); ll y=sum*c[i]; dfs(i,x,y);
while (!(x%c[i])){
x/=c[i]; y*=c[i];
dfs(i,x,y);
}
}
}
}
int main(){
scanf("%d",&n); m=(int)sqrt(n); int i,j;
for (i=2; i<=50000; i++){
if (!vis[i]) c[++cnt]=i;
for (j=1; j<=cnt && i*c[j]<=50000; j++){
vis[i*c[j]]=1;
if (!(i%c[j])) break;
}
}
ans=(ll)1073741824*2; dfs(1,n,1);
if (ans<=2147483647) printf("%lld
",ans);
else puts("-1");
return 0;
}
by lych
2016.2.22