제출 #4993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4993		lingxiang	분수 (KPI13_fractions)	C++98	0 / 1	0 ms	1088 KiB

fractions

/*
construct with farey sequence
*/

#include<stdio.h>
#include<string.h>

long long int a,b,c,d;
long long int fn1=0,fd1=1,fn2=1,fd2=1;
long long int numeric;
int T;

void input(){
	scanf("%d",&T);
}

void solve(){
	for(int i=0;i<T;i++){
		fn1=0,fn2=1,fd1=1,fd2=1;
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		if(a/b==c/d){
			numeric=a/b;
			a=a-b*numeric;
			c=c-d*numeric;
		}
		else{
			printf("%lld 1\n",a/b+1);
			continue;
		}
		while(1){
			//puts("*");
			long long int next_fn=fn1+fn2;
			long long int next_fd=fd1+fd2;
			if(next_fn*b<=next_fd*a){
				fn1=next_fn;
				fd1=next_fd;
			}
			else if(next_fd*c<=next_fn*d){
				fn2=next_fn;
				fd2=next_fd;
			}
			else{
				printf("%lld %lld\n",next_fn+next_fd*numeric,next_fd);
				break;
			}
		}
	}
}

void output(){

}

int main(){
	input();
	solve();
	output();
	return 0;
}

• Subtask 1: 0 / 1