https://www.acmicpc.net/problem/7121
K일간 작업하여 N + 1의 배수일에는 페인팅 작업을, M + 1의 배수일에는 바니싱 작업을 하지 않고 쉽니다.
1. 페인팅과 바니싱을 모두 완료한 날
2. 페인팅과 바니싱 둘다 쉰 날
3. 페인팅만 완료한 날
4. 바니싱만 완료한 날
위 값들을 순서대로 구하는 문제입니다.
우선 작업을 언제 쉬었는지에 대해서는 전체 일수에서 처음 쉬는날인 N + 1과 M + 1을 각각 나눠주면 구할 수 있습니다.
두 작업을 모두 완료한 날은 `전체 일 수 - 페인팅을 쉰 날 - 바니싱을 쉰 날 + 둘다 쉰 날`로 구할 수 있습니다.
둘다 쉰 날은 두 작업의 최소공배수를 활용하여 구할 수 있습니다.
둘중 하나만 완료한 날은 서로 반대 작업을 쉰날에서 둘다 쉰날을 빼면 구할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
using namespace std;
typedef long long ll;
ll N, M, K;
ll gcd(ll x, ll y) {
return y ? gcd(y, x % y) : x;
}
ll lcm(ll x, ll y) {
return x * y / gcd(x, y);
}
void func() {
ll x = K / (N + 1);
ll y = K / (M + 1);
ll z = K / lcm(N + 1, M + 1);
cout << K - x - y + z << ' ' << z << ' ' << y - z << ' ' << x - z << '\n';
}
void input() {
cin >> N >> M >> K;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |