취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3110번 문제인 부등식이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3110 

분모가 B, C, D인 분수의 분자를 각각 y, x, z라 하자.

주어지는 모든 정수가 1 이상 1000 이하이므로 가능한 x의 경우의 수는 100만가지 이하이다.

따라서, 각 x값마다 가능한 y의 개수, z의 개수를 구해 둘을 곱해 더하는 것으로 충분히 빠르게 답을 계산할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll ans = 0;
	ll A1, A2, B, C, D, E1, E2; cin >> B >> C >> D >> A1 >> A2 >> E1 >> E2;
	if (A1 * E2 < A2 * E1) {
		ll iterL = (A1 * C) / A2, iterR = (E1 * C) / E2;
		if ((E1 * C) % E2) iterR++;
		for (ll x = iterL; x < iterR; x++) {
			ll L1 = (A1 * B) / A2, R1 = (x * B) / C;
			if ((x * B) % C) R1++;
			ll L2 = x * D / C, R2 = E1 * D / E2;
			if ((E1 * D) % E2) R2++;
			ans += max(0LL, (R1 - L1 - 1)) * max(0LL, (R2 - L2 - 1));
		}

		cout << ans;
	}
	else cout << 0;
}