rt。。。
只要对代码有帮助的都会关注
感谢大佬
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define int long long
using namespace std;
const int N=8e5+15;
const long long INF=0x3f3f3f3f3f3f3f3fll;
inline void FileIO(){
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
template<typename Type>
inline void read(Type& res){
Type x=0,f=1; char c=' '; while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
res=x*f;
}
int x,y,cnt,bound,ans[N],num[N],Pow[N];
bool flag;
void Reduce(int &a,int &b){
int g=__gcd(a,b);
a/=g,b/=g;
}
void PrintAns(){
for(int i=1;i<=cnt;i++) printf("%lld ",ans[i]);
}
void dfs(int step,int a,int b){
if(step==cnt){
if(a==1&&b<ans[cnt]&&b>num[step-1]&&b<=bound){
num[cnt]=b;
for(int i=1;i<=cnt;i++) ans[i]=num[i];
return;
}
}
if(step==cnt-1){
int lz=4*b/a/a+1,rz=min(2*bound/a,bound*bound/b);
for(int z=lz;z<=rz;z++){
int delta=a*a*z*z-4*b*z;
int tmp=sqrt(delta);
if(tmp*tmp!=delta) continue;
if(delta%2!=a*z%2) continue;
num[cnt-1]=(a*z-tmp)/2;
num[cnt]=(a*z+tmp)/2;
if(num[cnt]<ans[cnt]){
for(int i=1;i<=cnt;i++) ans[i]=num[i];
return;
}
}
}
if(a==0) return;
if(a>(cnt-step+1)*Pow[cnt-step]) return;
if(b>Pow[cnt-step+1]) return;
int lbound=max(max(num[step-1]+1,bound*b/(bound*a-(cnt-step)*b)),(int)((b*1.0)/a+0.5));
int rbound=min(bound,b*(cnt-step+1)/a);
if(lbound>ans[cnt]) return;
for(int i=lbound;i<=rbound;i++){
int resa=a*i-b,resb=b*i;
if(resa<0||resb<0) continue;
Reduce(resa,resb);
num[step]=i;
// printf("%d/%d-%d/%d=%d/%d\n",a,b,1,i,resa,resb);
dfs(step+1,resa,resb);
// if(flag) return;
}
}
signed main(){
// 不开longlong见祖宗!
// 检查数组大小!
// 禁止在int乘int时不开longlong!
// STL数据类型拷贝赋值时间复杂度是 O(N)!
// freopen("Fraction.out","w",stdout);
memset(ans,0x3f,sizeof(ans));
read(x),read(y);
Reduce(x,y);
// printf("%d/%d\n",x,y);
Pow[0]=1;
for(cnt=2;cnt<=10000000;cnt++){
for(bound=100;bound<=10000000;bound*=10){
// printf("Cnt=%d,Bound=%d\n",cnt,bound);
// for(int i=1;i<=30;i++) puts("HAHAHAHAHHAHAHAHAHAHAHAHAHHAHAHAHAHAHAHAHHAHAHAHAHAHAHAHAHAHHAHA");
for(int i=1;i<=100;i++){
Pow[i]=Pow[i-1]*bound;
if(Pow[i]>1e15)
Pow[i]=1e15;
}
dfs(1,x,y);
if(ans[cnt]<=10000000+114514){
PrintAns();
return 0;
}
}
}
return 0;
}