#include <bits/stdc++.h> using namespace std; long long solve(vector <long long> &v, int idx, long long w, long long h) { while (v[idx] > w || v[idx] > h) idx--; long long x = w / v[idx], y = h / v[idx]; long long _w = w - x * v[idx], _h = h - y * v[idx]; if (_w == 0 && _h == 0) return y * x; else if (_w == 0) return y * x + solve(v, idx - 1, w, _h); else if (_h == 0) return y * x + solve(v, idx - 1, _w, h); else return y * x + solve(v, idx - 1, w - _w, _h) + solve(v, idx - 1, _w, h - _h) + solve(v, idx - 1, _w, _h); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long h, w; int n; cin >> h >> w >> n; vector <long long> v(n + 1); for (int i = 1; i <= n; i++) cin >> v[i]; if (h % v[1] != 0 || w % v[1] != 0) { cout << -1 << '\n'; return 0; } cout << solve(v, n, w, h) << '\n'; }
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 | #include <bits/stdc++.h> using namespace std; long long solve(vector <long long> &v, int idx, long long w, long long h) { while (v[idx] > w || v[idx] > h) idx--; long long x = w / v[idx], y = h / v[idx]; long long _w = w - x * v[idx], _h = h - y * v[idx]; if (_w == 0 && _h == 0) return y * x; else if (_w == 0) return y * x + solve(v, idx - 1, w, _h); else if (_h == 0) return y * x + solve(v, idx - 1, _w, h); else return y * x + solve(v, idx - 1, w - _w, _h) + solve(v, idx - 1, _w, h - _h) + solve(v, idx - 1, _w, _h); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long h, w; int n; cin >> h >> w >> n; vector <long long> v(n + 1); for (int i = 1; i <= n; i++) cin >> v[i]; if (h % v[1] != 0 || w % v[1] != 0) { cout << -1 << '\n'; return 0; } cout << solve(v, n, w, h) << '\n'; } |