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


그냥 풀다가 시간 초과가 뜨는 순간 말린다.
중간에 있는 ?에 먼저 값을 채워넣어주면, 나머지 2개의 ?를 채우는 과정은 일차부등식이기에 O(1)에 해결할 수 있다.
따라서, 전체 시간 복잡도는 O((E1/E2 - A1/A2) * C) 이다.


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24#include <iostream> #include <cstdint> int main() { using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); int B, C, D, A1, A2, E1, E2; cin >> B >> C >> D >> A1 >> A2 >> E1 >> E2; int64_t ans = 0; const int jl = A1 * C / A2 + 1, jr = (E1 * C - 1) / E2; for (int j = jl; j <= jr; ++j) { const int il = A1 * B / A2 + 1, ir = (j * B - 1) / C; const int kl = j * D / C + 1, kr = (E1 * D - 1) / E2; ans += (ir - il + 1) * int64_t(kr - kl + 1); } cout << ans << '\n'; return 0; }