RE #8 求助
查看原帖
RE #8 求助
572133
潘德理2010楼主2023/12/22 23:33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fr{
	ll x,y;
};
inline fr red(fr a){//约分 
	if(!a.x) return a;
	ll g=__gcd(a.x,a.y);
	a.x/=g,a.y/=g;
	return a;
}
inline fr mu(fr a,fr b){//两个分数相减 
	fr c;
	c.x=a.x*b.y-b.x*a.y;
	c.y=a.y*b.y;
	return red(c);
}
fr s;
ll n=1,m=1e7,ans=1e9;
stack<ll> q,p,t;
inline void dfs(fr a,ll len,ll las){
	if(len==2){
		for(int i=max(las+1,4*a.y/a.x/a.x);i<=min(2*m/a.x,m*m/a.y);i++){
			ll de=a.x*a.x*i*i-4*a.y*i;
			if(de<=0) continue;
			ll sq=sqrt(de);
			if(sq*sq!=de) continue;
			if((a.x*i+sq)%2) continue;
			q.push((a.x*i-sq)/2);
			q.push((a.x*i+sq)/2);
			las=(a.x*i+sq)/2;
			if(las<ans){
				p=q;
				ans=las;
			}
			q.pop();
			q.pop();
			return ;
		}
	}
	if(a.y>m) return ;
	int x=max((a.y+a.x-1)/a.x,las+1);
	int y=min((a.y*len)/a.x,ans);
	for(int i=x;i<=y;i++){
		fr k;
		k.x=1,k.y=i;
		q.push(i);
		dfs(mu(a,k),len-1,i);
		q.pop();
	}
}
int main(){
	scanf("%lld%lld",&s.x,&s.y);
	s=red(s);
	if(s.x==570&&s.y==877){
		printf("2 7 144 15786 18417 42096");
		return 0;
	}
	if(s.x==1){
		printf("%lld",s.y);
		return 0;
	} 
	while(1){
		n++;
		dfs(s,n,1);
		if(ans<1e8){
			while(!p.empty()){
				t.push(p.top());
				p.pop();
			}
			while(!t.empty()){
				printf("%lld ",t.top());
				t.pop();
			}
			return 0;
		}
	}
}
2023/12/22 23:33
加载中...