subtask#1tle求调,已经加了关于最后2个的优化
查看原帖
subtask#1tle求调,已经加了关于最后2个的优化
169594
Heart_Of_Iron_4楼主2025/1/7 20:29
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int gcd(int __m, int __n)
{
	while (__n != 0)
	{
		int __t = __m % __n;
		__m = __n;
		__n = __t;
	}
	return __m;
}
int a,b,t1,t2,t3,mi,maxn,ax,ppow[1145];
vector<int> ans;
inline int h(int x,int y,int z)
{
	return (1.0*x/y)/(1.0/(z+1));
}
//ofstream fout("1.out");
inline bool dfs(int x,int y,int z,int t)
{
	if(x!=1&&t==maxn)
	{
		return 0;
	}
	if(t>maxn)return 0;
	if(z>mi||z>ax)return 0;
	if(x==1)
	{
		if(y>ax)return 0;
		if(y>=mi)return 0;
		mi=y;
		ans.clear();
		ans.push_back(y);
		return 1;
	}
	if(t+h(x,y,z)>maxn)return 0;
	//if((maxn-t)*ppow[maxn-t-1]<x||y>ppow[maxn-t])return 0;
	if(t==maxn-2&&min(2*ax/a,ax*ax/b)<=10000)
	{
		for(int i=(4*y/x/x)+1;i<=min(2*ax/a,ax*ax/b);++i)
		{
			int delta=x*i*x*i-4*y*i,t,x1=0,x2=0;
			t=sqrt(delta);
			t=t+2;
			while(t*t>delta)t--;
			if(t*t==delta&&i*x>t&&(i*x-t)%2==0)
			{
				x1=(i*x-t)/2;
				x2=(i*x+t)/2;
				if(x2>ax||x2>=mi)continue;
				mi=x2;
				ans.clear();
				ans.push_back(x1);
				ans.push_back(x2);
				return 1;
			}
		}
		return 0;
	}
	bool fl=0,wn=0;
	for(int i=max(z+1,y/x);i<=ax;++i)
	{
		int fz=0,fm=0;
		fz=x*i-y;
		fm=y*i;
		if(fz<0)continue;
		t1=gcd(fm,fz);
		fz/=t1;
		fm/=t1;
		if(t+1>maxn)break;
		if(h(fz,fm,i)+t+1>maxn)break;
		fl=dfs(fz,fm,i,t+1);
		if(fl==1)
		{
			ans.push_back(i);
			wn=1;
		}
	}
	return wn;
}
signed main()
{
	scanf("%lld%lld",&a,&b);
	t1=gcd(a,b);
	a/=t1;
	b/=t1;
	mi=1145141919810;
	for(maxn=0;;++maxn)
	{
		for(ax=100000;ax<=10000100;ax*=10)
		{
			ppow[0]=1;
			for(int i=1;i<=maxn;++i)ppow[i]=ppow[i-1]*ax;
			if(dfs(a,b,0,0))
			{
				//reverse(ans.begin(),ans.end());
				sort(ans.begin(),ans.end());
				for(auto i:ans)
				{
					printf("%lld ",i);
				}
				return 0;
			}
		}
	}
	return 0;
}
2025/1/7 20:29
加载中...