Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "CAU1"
- #include <iostream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- int a, b, c;
- void Read()
- {
- cin >> a >> b >> c;
- if (a < b)
- swap(a, b);
- }
- // a >= sqrt(c)
- void Subtask_1()
- {
- int ans(0);
- for (int x = 1; 1ll * x * a < c; ++x)
- if ((c - x * a) % b == 0) // Tồn tại y thỏa mãn
- ++ans;
- cout << ans;
- }
- #define bit(i, c) (((c) >> (i)) & 1) // c_i
- void Subtask_2()
- {
- vector<vector<int>> f(__lg(c) + 3, vector<int>(a * __lg(c) + 3, 0));
- for (int i = 0; (1 << i) <= c; ++i)
- for (int j = 0; j <= i * a; ++j)
- {
- if (i == 0 && j == 0)
- ++f[i][j];
- if (j % 2 == bit(i, c))
- f[i + 1][j / 2] += f[i][j];
- if ((j + a) % 2 == bit(i, c))
- f[i + 1][(j + a) / 2] += f[i][j];
- if ((j + b) % 2 == bit(i, c))
- f[i + 1][(j + b) / 2] += f[i][j];
- if ((j + a + b) % 2 == bit(i, c))
- f[i + 1][(j + a + b) / 2] += f[i][j];
- }
- cout << f[__lg(c) + 1][0] - (c % b == 0) - (c % a == 0);
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Read();
- if (1ll * a * a >= c)
- Subtask_1();
- else
- Subtask_2();
- }
Add Comment
Please, Sign In to add comment