首先根据裴蜀定理,能走到的点 \(x\) 肯定满足 \(\gcd(a, b) | x\)。
于是令 \(g = \gcd(a, b)\),可以考虑求解 \(\lfloor\frac{m}{g}\rfloor, \frac{a}{g}, \frac{b}{g}\),最后记得去判一下 \([g\lfloor\frac{m}{g}\rfloor, m]\) 这个区间,因为只有这个区间是不满(区间长度可能 \(< g\))的,其他的直接 \(\times g\) 即可。
接下来的求解都以新的规模来做。
考虑到 \(+ a\) 这个操作,这启发可以类似同余最短路的想法,记录到 \(\bmod a = p(0\le p < a)\) 的点,要走到这样的点至少答案都得是多少,记为 \(mx_p\)。
然后 \(mx_p\) 是可以递推的,考虑从 \(-ib\bmod p\) 推到 \(-(i + 1)b\bmod p\),那么这一步推过去肯定就需要 \(-b\) 了,考虑在维护一下当 \(-ib\bmod p\) 时此时推到的数 \(x\) 的值,那么肯定需要 \(x\ge b\),所以先加 \(a\) 加到 \(x\ge b\),再 \(-b\) 即可,其中还没 \(-b\) 时 \(x\) 的最大值就是可能的最大值,与 \(mx_{-ib\bmod p}\) 取 \(\max\) 后即是 \(mx_{-(i + 1)b\bmod p}\)。
即初始化 \(x = 0, mx_0 = 0, i = 0\),接下来若 \(x < b\),则一直 \(+ a\) 直到 \(x\ge b\),然后 \(mx_{-(i + 1)b\bmod p} \leftarrow \max\{mx_{-ib\bmod p}, x\}\),最后 \(x\leftarrow x - b\)。
当然能够证明其实 \(-ib\bmod p = x\),这因为如果不成立显然有 \(x\ge a\),那么到了上一步肯定再 \(x\ge b + a\),但是上一步若 \(x \ge b\) 就停止了操作,肯定 \(x\in [b, b + a)\),所以不成立。
那么要表示出 \(i\) 需要的最小值就是 \(\max\{i, mx_{i\bmod a}\}\)。
通过递推过程能够发现 \(mx_p\le a + b\),所以当 \(i\ge a + b\) 时肯定需要的最小值就是 \(i\)。
所以可以考虑暴力处理出 \(x\in [0, a + b]\) 范围内的 \(f(x)\),前缀和即可。
对于 \(x\in (a + b, m]\) 肯定有 \(f(x) = x + 1\),用一个等差数列求和即可。
时间复杂度 \(\mathcal{O}(a + b)\)。
#include<bits/stdc++.h>
using ll = long long;
const int maxV = 2e5 + 10;
int mxp[maxV];
int cnt[maxV];
int main() {
int M, A, B;
scanf("%d%d%d", &M, &A, &B);
int g = std::__gcd(A, B);
int m = M / g, a = A / g, b = B / g;
for (int i = 0, p = 0, mx = 0; i < a; i++)
mxp[p] = mx, p < b && (p += (b - p + a - 1) / a * a), mx = std::max(mx, p), p -= b;
int n = std::min(m, a + b);
for (int i = 0; i <= n; i++)
cnt[std::max(i, mxp[i % a])]++;
for (int i = 1; i <= n; i++)
cnt[i] += cnt[i - 1];
ll ans = 0;
for (int i = 0; i <= n; i++)
ans += 1ll * cnt[i] * g;
if (m == n)
ans -= 1ll * cnt[m] * ((m + 1) * g - 1 - M);
else {
int l = n + 1, r = m - 1;
ans += 1ll * (l + r) * (r - l + 1) / 2ll * g;
ans += 1ll * m * (M - m * g + 1);
ans += M + 1 - (n + 1) * g;
}
printf("%lld\n", ans);
return 0;
}
标签:1146D,frac,int,bmod,Codeforces,ge,Jumping,ib,mx
From: https://www.cnblogs.com/rizynvu/p/18184947