554
CF27.E. Number With The Given Amount Of Divisors
這題讓求因子數為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;
}
最後更新：2017-04-04 07:03:44