我写了一个高精,里面一部分是用结构体封装的,但是放到递归里面,加了一个函数以后,递归就进不去了
#include<bits/stdc++.h>
using namespace std;
int n;
const int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};//2^20=65536>50000
struct Bignum
{
int len,d[100005];
void print()
{
for(int i=len;i>=1;i--) printf("%d",d[i]);
puts("");
}
bool operator<(const Bignum &p)const
{
if(len==0) return 0;
if(len<p.len) return 1;
for(int i=len;i;i--) if(d[i]!=p.d[i]) return d[i]<p.d[i];
return 0;
}
}ans;
Bignum times(Bignum a,int x)
{
for(int i=1;i<=a.len;i++) a.d[i]*=x;
for(int i=1;i<=a.len;i++) a.d[i+1]+=a.d[i]/10,a.d[i]%=10;
while(a.d[a.len+1])
{
a.len++;
a.d[a.len+1]+=a.d[a.len]/10;
a.d[a.len]%10;
}
return a;
}
Bignum Times(Bignum a,Bignum b)
{
Bignum res;
res.len=a.len+b.len-1;
for(int i=1;i<=a.len;i++) for(int j=1;j<=b.len;j++) res.d[i+j-1]+=a.d[i]*b.d[j];
for(int i=1;i<=res.len;i++) res.d[i+1]+=res.d[i]/10,res.d[i]%=10;
while(res.d[res.len+1])
{
res.len++;
res.d[res.len+1]+=res.d[res.len]/10;
res.d[res.len]%=10;
}
return res;
}
void dfs(Bignum x,int id,int num,int mx)
{
// printf("!!");
if(num>n) return ;
if(ans<x) return ;
if(num==n&&x<ans) ans=x;
Bignum poww;
poww.len=1,poww.d[1]=1;
for(int i=1;i<=mx;i++)
{
poww=times(poww,p[id]);
if(n%(num*(i+1))==0)
dfs(Times(poww,x),id+1,num*(i+1),i);//$###$
}
}
int main()
{
scanf("%d",&n);
Bignum One;
One.len=1,One.d[1]=1;
dfs(One,0,1,50000);
ans.print();
}
手调了一下,发现问题似乎出在dfs里面三个‘#’那里,删掉这句程序就可以输出两个感叹号,十分的迷……