86pts求助
查看原帖
86pts求助
731608
TeraniRetZiger楼主2022/6/27 12:23

rt.


using namespace std;

typedef long long ll;

typedef __int128 lll;

const int mod = 998244353; 

void print(lll n) {
	if (!n) return ;
	print(n / 10), putchar(n % 10 + 48);
}

struct vec {
	ll x, y;
	vec operator + (const vec &rhs) const { return { x + rhs.x, y + rhs.y }; }
};

inline 
bool inr(ll n, vec k) {
	return n < (lll)k.x * k.y;
}

inline 
bool steep(ll n, ll x, vec k) {
	return (lll)n * k.x <= (lll)x * x * k.y; 
}

stack<vec> s;

inline 
lll solve(ll n) {
	s.push({ 1, 0 }), s.push({ 1, 1 });
	ll cbr = cbrt(n), sqr = sqrt(n);
	vec p = { n / sqr, sqr + 1 };
	vec l, r, mid;
	lll ans = 0;
	for (;;) {
		l = s.top(); s.pop();
		while (inr(n, { p.x + l.x, p.y - l.y })) {
			ans += (lll)p.x * l.y + ((lll)(l.x - 1) * (l.y + 1) >> 1);
			p.x += l.x, p.y -= l.y;
		}
		if (p.y <= cbr) break;
		r = s.top();
		while (!inr(n, { p.x + r.x, p.y - r.y })) l = r, s.pop(), r = s.top();
		for (;;) {
			mid = l + r;
			if (inr(n, { p.x + mid.x, p.y - mid.y })) r = mid, s.push(mid);
			else if (steep(n, p.x + mid.x, r)) break;
			else l = mid;
		}
	}
	for (int i = 1; i < p.y; i++) ans += n / i;
	return ans * 2 - sqr * sqr;
}

ll l, r;

int main() {
	scanf("%lld%lld", &l, &r);
	printf("%lld", (ll)((solve(r) - solve(l - 1)) % mod));
}
2022/6/27 12:23
加载中...