boj 7121 Pencil Factory

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

 

K일간 작업하여 N + 1의 배수일에는 페인팅 작업을, M + 1의 배수일에는 바니싱 작업을 하지 않고 쉽니다.

 

1. 페인팅과 바니싱을 모두 완료한 날

2. 페인팅과 바니싱 둘다 쉰 날

3. 페인팅만 완료한 날

4. 바니싱만 완료한 날

위 값들을 순서대로 구하는 문제입니다.

 

우선 작업을 언제 쉬었는지에 대해서는 전체 일수에서 처음 쉬는날인 N + 1과 M + 1을 각각 나눠주면 구할 수 있습니다.

두 작업을 모두 완료한 날은 `전체 일 수 - 페인팅을 쉰 날 - 바니싱을 쉰 날 + 둘다 쉰 날`로 구할 수 있습니다.

둘다 쉰 날은 두 작업의 최소공배수를 활용하여 구할 수 있습니다.

둘중 하나만 완료한 날은 서로 반대 작업을 쉰날에서 둘다 쉰날을 빼면 구할 수 있습니다.

 

 

#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;
}