글 읽기 - 도대체 어디가 틀렸는지 잘 모르겠습니다ㅏㅏㅏ

wlsqudgk12 8년 전 0

ㅠㅠㅠㅠㅠㅠ 도와주세요

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>


using namespace std;

typedef unsigned long long  bigInt;

bigInt euclid(bigInt a, bigInt b) {
	for (; b != 0;) {
		bigInt tmpA = a;
		bigInt tmpB = b;

		a = b;
		b = tmpA % tmpB;
	}
	return a;
}

bool decomposition(bigInt& mother,bigInt& son,bigInt& x1son) {
	bigInt instMother = mother;
	bigInt instSon = son - x1son;


	int gcd = euclid(instSon, instMother);
	
	instSon /= gcd;
	instMother /= gcd;
	

	if (instMother >= 1000000) {
		return false;
	}
	else {
		mother = instMother;
		son = instSon;
		return true;
	}
}




int main() {
	
	bigInt son, mother;
	cin >> son >> mother;

	/*계속해서 구한다.*/
	while (son && mother) {
		vector<bigInt> answerList;

		while (son != 1) {
			bigInt reverse = mother / static_cast<double>(son);

			bigInt x1mother = reverse;
			bigInt x1son = 1;
			bigInt gcd;
			
			/*만약, 빼서 기약분수인 남은 수의 분모가 백만이 넘는지 확인하고,
			만약 백만이 넘으면 x1mother을 1증가시켜서 다시한번더 계산.
			만족시킬때 까지 계속 돎.*/
			while (true) {
				++x1mother;
				gcd = euclid(max(x1mother, mother), min(x1mother, mother));


				/*통분시킨다.*/
				bigInt tmpMother = mother;
				mother *= x1mother / gcd;
				son *= x1mother / gcd;

				
				
				x1son *= tmpMother / gcd;

				if (decomposition(mother, son, x1son)) {
					break;
				}
				mother /= x1mother / gcd;
				son /= x1mother / gcd;
				x1son /= tmpMother / gcd;
				if (son * x1mother >= 1000000) {
					for (int i = 1; i < son; ++i) {
						answerList.push_back(mother);
					}
					goto l1;
				}
					
			}

			answerList.push_back(x1mother);
		}
	l1:;
		answerList.push_back(mother);

		for (int i = 0; i < answerList.size(); ++i) {
			cout << answerList[i] << ' ';
		}
		cout << endl;

		cin >> son >> mother;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도대체 어디가 틀렸는지 잘 모르겠습니다ㅏㅏㅏ

wlsqudgk12 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말