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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// #include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    FAST
    uint64_t n,m, dn;
    cin >> n >> m >> dn;
    vector<uint64_t> d(dn);
    for (int i = 0; i < dn; i++)
    {
        cin >> d[i];
    }

    if (n%d[0] != 0 || m %d[0] != 0 ) {
        cout << -1;
        return 0;
    }
    uint64_t fit_n, fit_m;
    pair<uint64_t, uint64_t> curr;
    queue<pair<uint64_t,uint64_t>> to_split;
    queue<pair<uint64_t,uint64_t>> next_iteration;
    to_split.push({n,m});
    uint64_t total =0;

    for (int i = dn-1; i>=0; i--) {
        while (to_split.size()>0){
            curr = to_split.front();
            to_split.pop();
            fit_n = curr.first/d[i];
            fit_m = curr.second/d[i];
            total += fit_m*fit_n;
            // TODO: check XD
            if (fit_n * d[i] < curr.first) {
                next_iteration.push({
                    curr.first-fit_n * d[i],
                    curr.second,
                });
            }
            if (fit_m *d[i] < curr.second) {
                next_iteration.push({
                    fit_n * d[i],
                    curr.second-fit_m * d[i],
                });
            }
        }
        to_split = next_iteration;
        next_iteration = queue<pair<uint64_t,uint64_t>>();
    }
    cout << total;
}