글 읽기 - 반례를 못찾겠습니다.

kyunghooh76 5년 전 0

질문 검색에서 본문이나 댓글에 나온 반례는 다 돌려봤는데 제대로 나옵니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

typedef unsigned long long	UINT64;
typedef long long			INT64;

#define FOR(i, s, e) for(int i = (s); i < (e); i++)

UINT64 a, b;
vector<UINT64> pList;

UINT64 getNext(UINT64& parent)
{
	UINT64 bSum = 1;
	for (auto& i : pList)
		bSum *= i;
	UINT64 aSum = 0;
	for (auto& i : pList) {
		aSum += (bSum/i);
	}
	if (aSum == bSum)
		aSum = 1;

	UINT64 aSub = (a*bSum) - (aSum * b);
	UINT64 bSub = b * bSum;
	if (bSub  % aSub == 0) {
		parent = bSub / aSub;
		return 1;
	}
	parent = bSub / aSub + 1;
	return 0;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &a, &b);
		pList.clear();
		pList.push_back(b / a + 1);
		UINT64 parent = 0;
		while (getNext(parent) != 1) {
			pList.push_back(parent);
		}
		printf("%lld\n", parent);
	}
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

kyunghooh76 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말