没过hack在线求调
  • 板块P1763 埃及分数
  • 楼主why100
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/2/6 08:43
  • 上次更新2025/2/6 11:43:01
查看原帖
没过hack在线求调
316533
why100楼主2025/2/6 08:43
#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
typedef long long ll;
const ll N = 10,M = 1e7+715;
double h[M];
ll ft[N],bes[N],Ms = 1e7,Thr = 1000;
ll a,b,deep,cnt;
//the flag of find an answer
bool f;
#define CK ((a*1./b)  < (h[fa]-h[fa-de+deep+2]))
#define Ck (fa < (a*(deep-de+1)/b)) 
void P();
//<
//update
//要凑 a b 凑到fa 深度de 
string abut = ":%lld %lld %lld %lld\n";

void dfs(ll a,ll b,ll fa,ll de)
{
	if(de == deep-1)
	{
//		if(Ms*2/a <= Thr)
		{
			ll U = min(Ms*2/a,Ms*Ms/b);
//			cout << a<<' ' << b<<' '  << fa<<' '  << de << endl;
			for(int i = (b*4/a/a);i <=(U);i++)
			{
				ll ddd = (a*a*i*i-4*b*i);
				ll sq = sqrt(ddd);
//				cout << sq << ' '<< (long double)(a*a*i*i-4*b*i);//puts("--is sq");
				if(sq*sq == (ddd))
				{
					ll x2 = (sq+a*i)/2;
					ll x1 = (a*i-sq)/2;
					if((x2>x1))if(x2 < Ms)//(x1 > ft[de-1]) &&
					{
						f = 1;
						ft[de] = x1;ft[de+1] = x2;Ms = x2; 
						memcpy(bes,ft,sizeof(bes));
//						cout << x1 << ' ' <<x2 << ' ' << i;puts("--is xx"); 
						return;
					}
				}
			}
		}
	}
//	printf(&abut[0],a,b,fa,de);
	if(de == deep)
	{
//		puts("ass") ;
		if(a == 1)
		{
			if(b > fa)if(b < Ms){
				
				if((bes[deep] == 0) || (bes[deep] > ft[deep]))
				{
					ft[deep] = b;
					f = 1;
					memcpy(bes,ft,sizeof(bes));
					Ms = bes[deep];
				}
			}
		}
		return;
	}
	if(de > deep)return ;
	//a/b < 2/fr = (maxDep - dep + 1) * q / p;
	ll mma = min(Ms,(deep - de + 1) * b / a);
	for(fa = max(fa+1,(ll)(1.*b/a+1-1e-8));(fa <= mma) && CK;fa++)// (cmp(a,b,2,fa) == 1)&& 
	{
//		cnt++;
//		if(cnt > 4e8)
//		{
//			P();exit(0);
//		}
//		if(f)
//		{
			if(fa > Ms)return;
//		}
		
		ll ya = a*fa;
		if(ya < b)continue;
		if(ya == b)
		{
			ft[de] = fa;
			if((!f) || (bes[deep] > ft[deep]))
			{
				f = 1;
				memcpy(bes,ft,sizeof(bes));
				Ms = bes[deep];
			}
			return;
		}
		if(de == deep)continue;
		ll aa,bb;
		ft[de] = fa;
		aa = ya-b;bb = b*fa;
		ll c = aa,d = bb;
		bb = __gcd(c,d);
//		ll r = aa%bb;
//		while(r)
//		{
//			aa = bb;bb = r;r = aa%bb;
//		}
		c /= bb;d/=bb;
//		redu(aa,bb,a,b,1,fa);
//		printf("%%%lld %lld %lld %lld\n",1,fa,aa,bb);
		
		dfs(c,d,fa,de+1);
//		printf("out\n");
	}
}
int main()
{
//	freopen("1.txt","r",stdin);
	for(int i = 1e7;i > 1;i--)
	{
		h[i] = 1./i+h[i+1];
	}
//	cout << h[2];
	cin >> a >> b;
	for(ll i = 0;;i++)
	{
		ll ms;
		for(ms = 1e4;ms <= 1e7;ms*=10)
		{
	//		cout << i << endl;
			deep = i;
			Ms = ms;
			dfs(a,b,1,0);
			if(f)
			{
				P();
				return 0;
			}
		}
	}
	return 0;
} 
void P()
{
//	puts("---");
	for(ll i = 0;i <= deep;i++)
	{
		cout << bes[i] << ' ';
	}
//	puts("----");
}
2025/2/6 08:43
加载中...