Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #include <string>
  2. #include <time.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <bitset>
  6. #include <utility>
  7. #include <map>
  8. #include <set>
  9. #include <sstream>
  10. #include <iostream>
  11. #include <cmath>
  12. #include <deque>
  13.  
  14. #define pii pair<ll,ll>
  15. #define MOD 998244353
  16. #define mp make_pair
  17. #define X first
  18. #define Y second
  19. typedef long long ll;
  20. using namespace std;
  21. ll n,m,k, y, z, l, i, j, x, r;
  22. ll a[100500], b[100500];
  23. vector<ll> g[200500];
  24. ll dp[400500];
  25. ll gcd(ll a, ll b) {
  26. return b == 0 ? a : gcd(b,a%b);
  27. }
  28. void go(ll v) {
  29. if (v + x <= j && dp[v+x] == 0) {
  30. dp[v+x] = 1;
  31. r++;
  32. go(v + x);
  33. }
  34. if (v - y >= 0 && dp[v-y] == 0) {
  35. dp[v-y] = 1;
  36. r++;
  37. go(v - y);
  38. }
  39. }
  40. int main() {
  41. //freopen("input.txt", "r", stdin);
  42. ll m;
  43. cin >> m >> x >> y;
  44. ll p = gcd(x, y);
  45. dp[0] = 1;
  46. r = 1;
  47. ll ans = 1;
  48. for (int i = 1; i <= min(m, max(x, y) * 2); i++) {
  49. j = i;
  50. if (i >= x && dp[i-x] == 1) {
  51. dp[i] = 1;
  52. r++;
  53. go(i);
  54. }
  55. ans += r;
  56. }
  57. if (max(x, y) * 2 >= m) {
  58. cout << ans << endl;
  59. return 0;
  60. }
  61. ll st = max(x, y) * 2 + 1;
  62. ll xx = (m / p) * p;
  63. while (st % p != 0 && st <= m) {
  64. ans += st / p + 1;
  65. st++;
  66. }
  67. if (st > m) {
  68. cout << ans << endl;
  69. return 0;
  70. }
  71. st /= p;
  72. ans += (xx /p + st + 1) * (xx / p - st) / 2 * p;
  73. while (xx <= m) {
  74. ans += xx / p + 1;
  75. xx++;
  76. }
  77. cout << ans << endl;
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement