为什么MLE了,大佬!
  • 板块P5179 Fraction
  • 楼主xwh_hh
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/1/5 13:25
  • 上次更新2023/10/24 05:30:50
查看原帖
为什么MLE了,大佬!
359444
xwh_hh楼主2023/1/5 13:25
#include<bits/stdc++.h>
using namespace std;
struct num{
	long long son,mum;
};
long long gcd(long long a,long long b){
	if(a>b) swap(a,b);
	return a==0?b:gcd(a,b%a);
}
void doit(long long &_1,long long &_2){
	long long g=gcd(_1,_2);
	_1/=g,_2/=g; 
}
num get(num l,num r){
	doit(l.son,l.mum);
	doit(r.son,r.mum);
//	putchar(65);
	long long u=l.son,v=l.mum,x=r.son,y=r.mum;
//	cout<<u<<' '<<v<<' '<<x<<' '<<y<<'\n';
	if(u==0){
		long long k=y/x+1;
		return (num){1,k};
	}else if(u>=v){
		/*
		long long k=u/v;
		u-=k*v,x-=k*y;
		num g=get((num){y,x},(num){v,u});
		swap(g.son,g.mum);
		g.son+=g.mum*k;
		return g;
		*/
		 num tmp=get((num){y,x-u/v*y},(num){v,u%v});
		 tmp=(num){tmp.mum+u/v*tmp.son,tmp.son};
		 return tmp;
	}else{
		num k=get((num){y,x},(num){v,u});
		return (num){k.mum,k.son};
	}
}
num a,b;
int main(){
	while(cin>>a.son>>a.mum>>b.son>>b.mum){
		num u=get(a,b);
		cout<<u.son<<'/'<<u.mum<<'\n';
	}
	return 0;
}

MLE on #3~#10

2023/1/5 13:25
加载中...