用 \((x, y)\) 表示 \(Ax + By\),那么这个等价于 SB 树。
那么直接在 SB 树上二分,遍历一遍找到 \(n\) 个点就好了。可以采用类似线段树查询的方式。
于是现在还剩下一个子问题:给定 \(a, b\),求 \(ax + by \le n\) 且 \(\gcd(x, y) = 1\) 的正整数 \((x, y)\) 对数。
考虑莫反,可得为 \(\sum\limits_{p = 1}^n \mu(p) \sum\limits_{x = 1}^{\left\lfloor\frac{n}{ap}\right\rfloor} \left\lfloor\frac{\left\lfloor\frac{n}{p}\right\rfloor - ax}{b}\right\rfloor\)。
这个东西可以整除分块后类欧算。注意因为 \(-a\) 是负数,所以要变成 \((-a) \bmod b\),然后答案加上 \(\frac{n(n + 1)}{2} \times \frac{(-a) \bmod b - (-a)}{b}\)。
理论时间复杂度其实是 \(O(n \sqrt{n} \log n)\),但是跑得挺快的。
code
// Problem: F - Insert Addition
// Contest: AtCoder - AtCoder Regular Contest 123
// URL: https://atcoder.jp/contests/arc123/tasks/arc123_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
ll A, B, n, L, R, pr[maxn], tot, mu[maxn];
bool vis[maxn];
namespace EL {
struct node {
ll cntx, cnty, sum;
node(ll a = 0, ll b = 0, ll c = 0) : cntx(a), cnty(b), sum(c) {}
};
inline node operator + (const node &a, const node &b) {
node res;
res.cntx = a.cntx + b.cntx;
res.cnty = a.cnty + b.cnty;
res.sum = a.sum + b.sum + a.cnty * b.cntx;
return res;
}
inline node qpow(node a, ll p) {
node res;
while (p) {
if (p & 1) {
res = res + a;
}
a = a + a;
p >>= 1;
}
return res;
}
node solve(ll p, ll q, ll r, ll n, node a, node b) {
if (!n) {
return node();
}
if (p >= q) {
return solve(p % q, q, r, n, a, qpow(a, p / q) + b);
}
ll cnt = ((lll)n * p + r) / q;
if (!cnt) {
return qpow(b, n);
}
return qpow(b, (q - r - 1) / p) + a + solve(q, p, (q - r - 1) % p, cnt - 1, b, a) + qpow(b, n - ((lll)q * cnt - r - 1) / p);
}
inline ll calc(ll p, ll q, ll r, ll n) {
ll ans = 0;
if (p < 0) {
ll t = (p % q + q) % q;
ans -= n * (n + 1) / 2 * ((t - p) / q);
p = t;
}
node a(0, 1), b(1, 0);
node res = qpow(a, r / q) + solve(p, q, r % q, n, a, b);
ans += res.sum;
return ans;
}
}
inline ll calc(ll a, ll b) {
ll ans = 0;
for (int i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
ans += EL::calc(-a, b, n / i, n / a / i) * (mu[j] - mu[i - 1]);
}
return ans;
}
vector<ll> ans;
void dfs(int lx, int ly, int rx, int ry) {
int mx = lx + rx, my = ly + ry;
if (A * mx + B * my > n) {
return;
}
dfs(lx, ly, mx, my);
ans.pb(A * mx + B * my);
dfs(mx, my, rx, ry);
}
void dfs(int lx, int ly, int rx, int ry, ll l, ll r) {
if ((int)ans.size() >= R - L + 1) {
return;
}
if (L <= l && r <= R) {
dfs(lx, ly, rx, ry);
ans.pb(A * rx + B * ry);
return;
}
int mx = lx + rx, my = ly + ry;
if (A * mx + B * my > n) {
return;
}
ll t = l + calc(A * lx + B * ly, A * mx + B * my);
if (L <= t) {
dfs(lx, ly, mx, my, l, t);
}
if (t < R) {
dfs(mx, my, rx, ry, t + 1, r);
}
}
void solve() {
scanf("%lld%lld%lld%lld%lld", &A, &B, &n, &L, &R);
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
pr[++tot] = i;
mu[i] = -1;
}
for (int j = 1; j <= tot && i * pr[j] <= n; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
mu[i * pr[j]] = 0;
break;
}
mu[i * pr[j]] = -mu[i];
}
}
for (int i = 1; i <= n; ++i) {
mu[i] += mu[i - 1];
}
ll t = calc(A, B) + 1;
--R;
if (L == 1) {
ans.pb(A);
} else {
--L;
}
dfs(1, 0, 0, 1, 1, t);
for (ll x : ans) {
printf("%lld ", x);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Addition AtCoder Regular Contest Insertaddition atcoder regular contest addition atcoder contest prefix atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 164 atcoder regular contest builder