Skip to content

Instantly share code, notes, and snippets.

@stevenhao
Created April 20, 2019 20:36
Show Gist options
  • Save stevenhao/8c34d20b6e18053ccafd8a51d11c9990 to your computer and use it in GitHub Desktop.
Save stevenhao/8c34d20b6e18053ccafd8a51d11c9990 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
int m, a, b;
typedef long long ll;
int cnt = 0;
ll ans = 0;
int mx = 0;
const int MAXN = 100100;
bool vis[MAXN];
void bfs() {
int cur = 0;
while (!vis[cur]) {
vis[cur] = true;
if (cur > m) {
ans += ll(m - mx) * cnt;
break;
}
if (cur > mx) {
ans += ll(cur - mx) * cnt;
mx = cur;
}
++cnt;
if (cur >= b) cur -= b;
else cur += a;
}
}
int gg(int a, int b) {
if (a == 0) return b;
return gg(b % a, a);
}
int main() {
cin >> m >> a >> b;
bfs();
int g = gg(a, b);
for(int i = 0; i < a; i += g) {
ll first = mx - mx % a + i;
if (first < mx) first += a;
ll last = m - m % a + i;
if (last > m) last -= a;
ll lo = first / a + 1;
ll hi = last / a;
ans += (lo - 1) * (first - mx); // [mx, first): lo - 1
ans += a * ((lo + hi) * (hi - lo + 1)) / 2; // [first, last): lo...hi
ans += (m - last + 1) * hi; // [last, m]: hi+1
}
cout << ans << "\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment