QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262892#5477. Cake Decorationxaphoenix#AC ✓2335ms3560kbC++172.5kb2023-11-24 11:26:272023-11-24 11:26:29

Judging History

你现在查看的是最新测评结果

  • [2023-11-24 11:26:29]
  • 评测
  • 测评结果:AC
  • 用时:2335ms
  • 内存:3560kb
  • [2023-11-24 11:26:27]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repn(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = (n) - 1; i >= a; i--)
#define pern(i, a, n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 110000;
const int M = 1100000;
const int mod = 998244353;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

LL x, l, r;
LL cal(LL v) {
	LL res = 0;
	for (LL b = 1; b * (b + 1) * (b + 2) <= x; b++) {
		LL va = min(x / (b * (b + 1) * (b + 2)), b - 1);
		for (LL a = 1; a <= va; a++) {
			LL lim = x / (a * b);
			LL l = b + 1, r = sqrtl(lim);
			while ((r + 1) * (r + 2) <= lim) r++;
			while (r * (r + 1) > lim) r--;
			if (l > r) continue;
			// AB
			if (a + b <= v) res = (res + r - l + 1) % mod;
			// AC
			if (l <= min(r, v - a)) res = (res + min(r, v - a) - l + 1) % mod;
			// AD
			if (a + lim / r <= v) {
				LL ll = l, rr = r, pos;
				while (ll <= rr) {
					LL mid = (ll + rr) / 2;
					if (a + lim / mid <= v) rr = mid - 1, pos = mid;
					else ll = mid + 1;
				}
				res = (res + r - pos + 1) % mod;
			}
			// BC
			if (l <= min(v - b, r)) res = (res + min(v - b, r) - l + 1) % mod;
			// BD
			if (b + lim / r <= v) {
				LL ll = l, rr = r, pos;
				while (ll <= rr) {
					LL mid = (ll + rr) / 2;
					if (b + lim / mid <= v) rr = mid - 1, pos = mid;
					else ll = mid + 1;
				}
				res = (res + r - pos + 1) % mod;
			}
			// CD
			if (lim / r + r <= v) {
				LL ll = l, rr = r, pos;
				while (ll <= rr) {
					LL mid = (ll + rr) / 2;
					if (mid + lim / mid <= v) rr = mid - 1, pos = mid;
					else ll = mid + 1;
				}
				res = (res + r - pos + 1) % mod;
			}
		}
	}
	return res;
}
int main() {
	IO;
	cin >> x >> l >> r;
	LL ans = (cal(r - 1) - cal(l - 1) + mod) % mod * 4 % mod;
	cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3376kb

input:

24 4 6

output:

12

result:

ok single line: '12'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3388kb

input:

30 5 6

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3300kb

input:

30 9 20

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1295ms
memory: 3360kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3296kb

input:

51256 4 35

output:

29116

result:

ok single line: '29116'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

5845 10 163

output:

10724

result:

ok single line: '10724'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3328kb

input:

47139 6 167

output:

71716

result:

ok single line: '71716'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3384kb

input:

20603 5 167

output:

36556

result:

ok single line: '36556'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3292kb

input:

37521 1 76

output:

46956

result:

ok single line: '46956'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3384kb

input:

1 1 10

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1278ms
memory: 3392kb

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

score: 0
Accepted
time: 1160ms
memory: 3328kb

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

score: 0
Accepted
time: 1179ms
memory: 3384kb

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

score: 0
Accepted
time: 1199ms
memory: 3296kb

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

score: 0
Accepted
time: 1244ms
memory: 3548kb

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

score: 0
Accepted
time: 1245ms
memory: 3432kb

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

score: 0
Accepted
time: 1189ms
memory: 3300kb

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

score: 0
Accepted
time: 1254ms
memory: 3560kb

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0
Accepted
time: 1206ms
memory: 3384kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

score: 0
Accepted
time: 1283ms
memory: 3400kb

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

score: 0
Accepted
time: 1446ms
memory: 3300kb

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

score: 0
Accepted
time: 1364ms
memory: 3328kb

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

score: 0
Accepted
time: 1315ms
memory: 3348kb

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

score: 0
Accepted
time: 1390ms
memory: 3328kb

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

score: 0
Accepted
time: 1270ms
memory: 3544kb

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

score: 0
Accepted
time: 287ms
memory: 3384kb

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

score: 0
Accepted
time: 399ms
memory: 3384kb

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

score: 0
Accepted
time: 229ms
memory: 3396kb

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

score: 0
Accepted
time: 1371ms
memory: 3328kb

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0
Accepted
time: 1411ms
memory: 3328kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

score: 0
Accepted
time: 243ms
memory: 3348kb

input:

100000000000000 1 2

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 2335ms
memory: 3428kb

input:

100000000000000 10000000000000 100000000000000

output:

36

result:

ok single line: '36'