有关递归爆掉的玄学问题
  • 板块学术版
  • 楼主ybe2007
  • 当前回复19
  • 已保存回复19
  • 发布时间2022/5/24 15:04
  • 上次更新2023/10/28 00:43:23
查看原帖
有关递归爆掉的玄学问题
78229
ybe2007楼主2022/5/24 15:04

我写了一个高精,里面一部分是用结构体封装的,但是放到递归里面,加了一个函数以后,递归就进不去了

#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里面三个‘#’那里,删掉这句程序就可以输出两个感叹号,十分的迷……

2022/5/24 15:04
加载中...