这题让求因子数为n的数中的最小的值。思路是先把n质因子分解成x1*x2*x3*x4...(注意x1,x2,x3,x4可能有相等情况)这种形式,然后把n的所有因子由大到小排序,然后可以还原成素数乘方的形式 ans=2^(x1-1)*3^(x2-1)*5^(x3-1)... 但是要注意的是这个答案可能是最终答案,但是有特例,比如8=2*2*2 根据上一个公式计算的ans=2^1*3^1*5^1=30 但是如果把8分成4*2 那么ans=2^3*3^1=24这样是最优解 因为2^1*5^1>2^3 所以先通过一个循环找出n的最优因子分解,可能不是质因子,再根据公式ans=2^(x1-1)*3^(x2-1)*5^(x3-1)...就是答案 最后注意精度问题就可以了 这题小题大做了 用了rho启发式质因子分解 也可以用素数表打出1000以内的素数来进行质因子分解
#include <iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long int64; int64 gcd(int64 a,int64 b) { if (a==0) return 1; if(a<0) return gcd(-a,b); if(b==0) return a; return gcd(b,a%b); } int64 modmult(int64 a,int64 b,int64 n)//a*b%n { a%=n; int64 ret; for(ret=0; b; a=(a<<1)%n,b>>=1) if(b&1) ret=(ret+a)%n; return ret; } int64 modular(int64 a,int64 b,int64 n)//renturn a^b%n { int64 ans=1; a%=n; while(b) { if(b&1) ans=modmult(ans,a,n),b--; b>>=1; a=modmult(a,a,n); } return ans; } bool witness(int64 a,int64 n)//判断 a^(n-1)=1(mod n) { int t=0; int64 x,xi,temp=n-1; while(temp%2==0) t++,temp/=2; xi=x=modular(a,temp,n); for(int i=1; i<=t; i++) { xi=modmult(xi,xi,n); if(xi==1&&x!=1&&x!=n-1) return 1; x=xi; } if(xi!=1) return 1; return 0; } bool millar_rabin(int64 n,int s) { for(int j=1; j<=s; j++) { int64 a=rand()%(n-1)+1;//a=rand()%(Y-X+1)+X; /*n为X~Y之间的随机数 if(witness(a,n)) return 0; } return 1; } int64 pollard_rho(int64 n,int64 c) { int64 i=1,k=2,x,y; x=rand()%n; y=x; while(1) { i++; x=(modmult(x,x,n)+c)%n; int64 d=gcd(y-x,n); if(d!=1&&d!=n) return d; if(x==y) return n; if(i==k) { y=x; k+=k; } } } int64 factor[100]; int tol; void findfac(int64 n) { if(millar_rabin(n,10)) { factor[tol++]=n; return; } int64 p=n; while(p>=n) p=pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); } void exgcd(long long a,long long b,long long &d,long long &x,long long &y) { if(b==0) { x=1; y=0; d=a; return; } else { exgcd(b,a%b,d,x,y); long long temp=x; x=y; y=temp-(a/b)*y; } } int cmp(int64 a,int64 b) { return a>b; } bool isprime[2000]; int nprime,prime[2000]; void getprime() { long long i,j; memset(isprime,1,sizeof(isprime)); isprime[1]=0; nprime=0; for(i=2; i<2000; i++) { if(isprime[i]) { prime[++nprime]=i; for(j=i*i; j<2000; j+=i) isprime[j]=0; } } } int main() { long long n; getprime(); while(cin>>n) { if(n==1) { cout<<1<<endl; continue; } tol=0; findfac(n); sort(factor,factor+tol,cmp); long long ans=1; for(int i=0; i<tol; i++) for(int j=i+1; j<tol; j++) { if(pow(prime[i+1],factor[i]*factor[j]-1)<pow(prime[i+1],factor[i]-1)*pow(prime[j+1],factor[j]-1)) { factor[i]*=factor[j]; factor[j]=1; for(int k=j; k<tol-1; k++) swap(factor[k],factor[k+1]); } } for(int i=0; i<tol; i++) ans*=(int64)(pow(prime[i+1],factor[i]-1)+1e-14); cout<<ans<<endl; } return 0; }