#include <bits/stdc++.h> #define ll long long #define fors(u, n, s) for(ll u = (s); u < (n); u++) #define foru(u, n) fors(u, n, 0) #define vec vector #define pb push_back #define f first #define s second #define ir(a, b, x) (((a) <= (x)) && ((x) <= (b))) #define pint pair<ll, ll> using namespace std; const int N = 30; ll h; ll w; ll n; ll d[N]; ll solve_ideal(ll idx, ll y){ ll out = 0; ll idx_ = idx; while(idx_ >= 0){ ll y_cnt = y/d[idx_]; y -= y_cnt*d[idx_]; out += y_cnt*d[idx]/d[idx_]; idx_ --; } return out; } ll solve(ll x, ll y){ ll out = 0; ll idx = n-1; while(idx >= 0){ ll cnt = x/d[idx]; x -= cnt*d[idx]; out += cnt*solve_ideal(idx, y); idx --; } return out; } int main() { cin >> h >> w >> n; foru(i, n) cin >> d[i]; if(w%d[0] != 0 || h%d[0] != 0){ cout << -1; return 0; } cout << solve(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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <bits/stdc++.h> #define ll long long #define fors(u, n, s) for(ll u = (s); u < (n); u++) #define foru(u, n) fors(u, n, 0) #define vec vector #define pb push_back #define f first #define s second #define ir(a, b, x) (((a) <= (x)) && ((x) <= (b))) #define pint pair<ll, ll> using namespace std; const int N = 30; ll h; ll w; ll n; ll d[N]; ll solve_ideal(ll idx, ll y){ ll out = 0; ll idx_ = idx; while(idx_ >= 0){ ll y_cnt = y/d[idx_]; y -= y_cnt*d[idx_]; out += y_cnt*d[idx]/d[idx_]; idx_ --; } return out; } ll solve(ll x, ll y){ ll out = 0; ll idx = n-1; while(idx >= 0){ ll cnt = x/d[idx]; x -= cnt*d[idx]; out += cnt*solve_ideal(idx, y); idx --; } return out; } int main() { cin >> h >> w >> n; foru(i, n) cin >> d[i]; if(w%d[0] != 0 || h%d[0] != 0){ cout << -1; return 0; } cout << solve(h, w); return 0; } |