自动搬运

查看原文

来自洛谷，原作者为

	da32s1da **

搬运于2025-08-24 22:03:33，当前版本为作者最后更新于2018-07-24 10:06:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最多有10个质数，因为$$23571113171923*29=6469693230$$ 一个质数最多有30个，因为$$2^{31}=2147483648$$ 均大于等于$2^{31}$，故应为$-1$。

可见，本题数据范围较小，可用$dfs$来完成。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define LL long long
int tot,vis[46500];
LL prime[4800];
void init(){  //预处理素数
	prime[++tot]=2;
	for(int i=3;i<=46400;i+=2)
	if(!vis[i]){
		prime[++tot]=i;int qq=i<<1;
		for(int j=i*3;j<=46400;j+=qq)
		if(!vis[j])vis[j]=1;
	}
	//4796 primes
}
LL n,ans=4294967296;
bool pr(LL qq){  //判断单个数字是否为素数
	if(qq&1^1)return false;
	int rr=sqrt(qq);
	for(int i=3;i<=rr;i+=2)
	if(qq%i==0)return false;
	return true;
}
void dfs(int pri,LL num,LL phi){
	if(num==1){  //若该数已经被拆完，直接更新答案
		ans=min(ans,phi);
		return;
	}
	if(num>sqrt(n)&&pr(num+1)){  //若当前数大于sqrt(n)，那么可能为质数且只有一个，故进行判断
		ans=min(ans,phi*(num+1)); //若是质数直接更新答案
        return;
	}
	for(int i=pri+1;i<=tot&&(prime[i]-1)<=num;i++) //枚举所有质数
	if(num%(prime[i]-1)==0){
		LL num_=num/(prime[i]-1);
		LL phi_=phi*prime[i];  //计算新的数字和答案
		dfs(i,num_,phi_);  //下一轮dfs
		while(num_%prime[i]==0){//枚举该质数的次数
			num_/=prime[i];   //计算新的数字和答案
			phi_*=prime[i];
			dfs(i,num_,phi_);  //下一轮dfs
		}
	}
}
int main(){
	init();   //得到sqrt(2147483647)以内的质数 
	scanf("%d",&n);
	dfs(0,n,1);  //进行dfs，一定要初始化答案为1
	if(ans!=4294967296)printf("%lld\n",ans);
	else puts("-1");  //输出答案
}