//Solution by Mikołaj Kołek #include "bits/stdc++.h" #define intin *istream_iterator<int>(cin) using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int h = intin, w = intin, n = intin; vector<int> d(n); copy_n(istream_iterator<int>(cin), n, d.begin()); sort(d.begin(), d.end()); if(h % d[0] != 0 or w % d[0] != 0) { cout << -1; return 0; } function<long long(int, int)> check = [&] (long long curH, long long curW) { if(curH == 0 or curW == 0) return 0ll; for(int i = d.size() - 1; i >= 0; i--) { if(d[i] <= curH and d[i] <= curW) { long long result = (curH / d[i]) * (curW / d[i]); result += check(curH - (curH % d[i]), curW % d[i]); result += check(curH % d[i], curW); return result; } } return 0ll; }; cout << check(h, w); return 0; }
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 | //Solution by Mikołaj Kołek #include "bits/stdc++.h" #define intin *istream_iterator<int>(cin) using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int h = intin, w = intin, n = intin; vector<int> d(n); copy_n(istream_iterator<int>(cin), n, d.begin()); sort(d.begin(), d.end()); if(h % d[0] != 0 or w % d[0] != 0) { cout << -1; return 0; } function<long long(int, int)> check = [&] (long long curH, long long curW) { if(curH == 0 or curW == 0) return 0ll; for(int i = d.size() - 1; i >= 0; i--) { if(d[i] <= curH and d[i] <= curW) { long long result = (curH / d[i]) * (curW / d[i]); result += check(curH - (curH % d[i]), curW % d[i]); result += check(curH % d[i], curW); return result; } } return 0ll; }; cout << check(h, w); return 0; } |