Frog Jumping
题目链接：http://codeforces.com/contest/1146/problem/D
数据范围：略。
题解：
首先发现，如果$x\ge a +b$，那么所有的$Num | gcd(a,b)$都可以取到。
这是显然的因为我们可以保证最右端点在$a+b$内。
那么我们只需要考虑小于$x$的部分。
可以暴力建边，跑出当前点需要的最右端点的最小值，用spfa或者堆优化dij都行。
代码：
#include <bits/stdc++.h>
#define N 1000010
using namespace std;
typedef long long ll;
int tag[N];
int head[N], to[N << 1], nxt[N << 1], tot;
inline void add(int x, int y) {
to[ ++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
int dis[N];
bool vis[N];
queue <int> q;
void spfa(int a, int b) {
memset(dis, 0x3f, sizeof dis);
dis[0] = 0;
q.push(0);
vis[0] = 1;
while (!q.empty()) {
int x = q.front();
vis[x] = false;
q.pop();
int pre = x - b, aft = x + a;
if (pre >= 0 && max(dis[x], pre) < dis[pre]) {
dis[pre] = max(dis[x], pre);
if (!vis[pre]) {
q.push(pre);
vis[pre] = true;
}
}
if (aft <= a + b && max(dis[x], aft) < dis[aft]) {
dis[aft] = max(dis[x], aft);
if (!vis[aft]) {
q.push(aft);
vis[aft] = true;
}
}
}
}
int f[N];
int main() {
int x, a, b;
cin >> x >> a >> b ;
spfa(a, b);
// puts("Fuck");
int d = __gcd(a, b);
if (x <= a + b) {
for (int i = 0; i <= x; i += d) {
if (dis[i] != 0x3f3f3f3f) {
tag[dis[i]] ++ ;
}
}
for (int i = 1; i <= x; i ++ ) {
tag[i] += tag[i - 1];
}
long long ans = 0;
for (int i = 0; i <= x; i ++ ) {
ans += tag[i];
}
cout << ans << endl ;
return 0;
}
// puts("A");
for (int i = 0; i <= a + b; i += d) {
// printf("%d\n", dis[i]);
if (dis[i] != 0x3f3f3f3f) {
tag[dis[i]] ++ ;
}
}
// puts("B");
for (int i = 1; i <= a + b; i ++ ) {
tag[i] += tag[i - 1];
}
// puts("C");
ll ans = 0;
for (int i = 0; i <= a + b; i ++ ) {
ans += tag[i];
}
// cout << ans << endl ;
int id = 0;
for (int i = a + b + 1; i <= x; i ++ ) {
if (i % d == 0) {
id = i;
break;
}
ans += i / d + 1;
// cout << ans << endl ;
}
if (!id) {
cout << ans << endl ;
return 0;
}
// cout << id << endl ;
int bg = id / d, ed = x / d;
ans += (ll)(bg + ed + 1) * (ed - bg) / 2 * d;
ans += (ll)(x - (ll)ed * d + 1) * (ed + 1);
cout << ans << endl ;
return 0;
}