글 읽기 - 문제이해가 부족하고 접근방법을 모르겠습니다!

polohee81 5년 전 1

먼저, 예시에서 원하는 값을 구하는 데까지는 성공했습니다. 그러나 문제에서 정확히 어떤것을 요구하는지 잘모르겠고, 어떤식으로 접근해야 될지도 잘 모르겠습니다.

각 주사위 마다 mod 를이용한 값을 도출한뒤에 그값들을 더해가는 방식 인가요?

혹은, 각 주사위에 대한 N 과 S값을 축척한뒤에 최종 주사위를 던진뒤에 값을 도출해야 하나요?

2. 기약분수로 표현되지 않는 분수 형태는 없는데, 그럼 <출력> 부분에서 요구하는 "대신" 출력한다. 라는 말은 의미가 없는것이 아닌가 생각이드는데

제생각이 틀렸나요..?

아주오래 생각해보고, 여러형태로 제출도 해보았지만, 감을 못잡아서 질문글 올립니다 !

정확히 어떤 질문을 해야 할지 .. 문제에 이해를 주시면 감사하겠습니다 !

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

// arr[1] = 어떤수의 2^1 = 2 승 
// arr[2] = 어떤수의 2^2 = 4 승
long long arr[60];
long long DIV = 1000000007;

// 어떤수의 x 승을 리턴
long long fuc(long long x) {
	int size = log2(x);
	long long tmp = 1;
	for (int i = 1; i <= size; i++) {
		tmp *= 2;
	}
	if (pow(2, size) == x && size < 60) {
		return arr[size];
	}
	else if (x == 1) {
		return arr[0];
	}
	else if (x == 0) {
		return 1;
	}

	return ((fuc(tmp) % DIV) * (fuc(x - tmp) % DIV)) % DIV;
}


// 최대공약수
int GCM(long long x, long long y)
{
	int n;
	while (1) {
		n = x % y;
		if (n == 0) return y;
		x = y;
		y = n;
	}
}

int main() {
	long long M, N = 0, S = 0, data1, data2;
	long long ans = 0;
	cin >> M;
	while (M--) {
		cin >> N >> S;

		// 배열초기화
		for (int i = 0; i < 60; i++) {
			arr[i] = 0;
		}

		// 최대공약수로 기약분수로 만들어 준다.
		long long gcm;
		gcm = GCM(N, S);
		N /= gcm;
		S /= gcm;

		// N의 DIV - 2 승을 구한다
		arr[0] = N % DIV;
		for (int i = 1; i < 60; i++) {
			arr[i] = ((arr[i - 1] % DIV)* (arr[i - 1] % DIV)) % DIV;
		}
		ans += (S * fuc(DIV - 2)) % DIV;
	}

	// 출력
	cout << ans << endl;
}

djm03178 5년 전 1

각 주사위의 기댓값을 x/y로 표현할 수 있으니, 그 기댓값을 전부 합해주면 됩니다. 단, 현재까지의 분모와 분자를 각각 따로 저장하면서 진행해야 합니다.
원래는 기댓값을 출력해야 하는데, 그 기댓값 자체를 출력하는 것 대신에 (a × b^-1) mod 1,000,000,007 를 출력하라는 것입니다.

polohee81 5년 전 0

답변 정말 감사합니다. 친절한 답변에 무색하게도 제가 .. 죄송하지만 아직 이해가 가지 않습니다.

3 7

5 9

라고 입력 하였을때

각 기대값은 7/3, 9/5 를 더하는 과정에서 통분을 하여 62 / 15 - > 분자 : 62 , 분모 : 15 라는 값을 가지고 있고

그후 최종 주사위를 던진뒤 저장된 분자와 분모를 사용하여 기댓값을 출력하라는 말씀이신가요?

djm03178 5년 전 1

네, 그렇습니다. 기약분수가 62 / 15이므로 a = 62, b = 15에 대해 (a × b^-1) mod 1,000,000,007 를 구하면 됩니다.

polohee81 5년 전 0

답변 정말 감사드립니다. 해결 할 수 있을 것 같습니다!

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

문제

문제

출처

ICPC

문제이해가 부족하고 접근방법을 모르겠습니다!

polohee81 5년 전 1

djm03178 5년 전 1

polohee81 5년 전 0

djm03178 5년 전 1

polohee81 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말