QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#262892 | #5477. Cake Decoration | xaphoenix# | AC ✓ | 2335ms | 3560kb | C++17 | 2.5kb | 2023-11-24 11:26:27 | 2023-11-24 11:26:29 |
Judging History
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'