QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173745 | #5477. Cake Decoration | Forever_Young# | AC ✓ | 1111ms | 3716kb | C++14 | 3.8kb | 2023-09-10 01:36:22 | 2023-09-10 01:36:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
const LL mod = 998244353;
LL a[4], b[4];
inline LL min_denom(LL a, LL c) {
return c >= 0 ? a / (c + 1) + 1 : mod * mod;
}
inline LL intsq(LL x) {
LL res = LL(sqrt(x));
while(res * res > x) {
res--;
}
while((res + 1) * (res + 1) <= x) {
res++;
}
return res;
}
LL calc(LL X, LL R) {
LL res = 0;
auto calc = [&]() {
memcpy(b, a, sizeof(b));
do {
if(b[0] + b[1] < R) {
res++;
}
} while(next_permutation(b, b + 4));
res %= mod;
};
for(a[0] = 1; a[0] <= 3162; a[0]++) {
//cout << a[0] << endl;
for(a[1] = a[0] + 1; a[0] * a[1] * a[1] * a[1] <= X; a[1]++) {
//cout << a[0] << ' ' << a[1] << ':' << res << endl;
LL cmin = a[1] + 1, cmax = intsq(X / a[0] / a[1]);
//cout << cmin << '?' << cmax << endl;
if(cmax == X / a[0] / a[1] / cmax) {
cmax--;
}
if(cmin > cmax) continue;
/*a[2] = cmin;
a[3] = X / a[0] / a[1] / a[2];
calc();
if(cmax > cmin) {
a[2] = cmax;
a[3] = X / a[0] / a[1] / a[2];
calc();
}
cmin++;
cmax--;
if(cmin > cmax) continue;*/
if(a[0] != a[1]) {
if(a[0] + a[1] < R) {
res = (res + (cmax - cmin + 1) * 4) % mod;
}
LL rm = R - a[0] - 1;
rm = min(rm, cmax);
if(rm >= cmin) {
res = (res + (rm - cmin + 1) * 4) % mod;
}
rm = R - a[1] - 1;
rm = min(rm, cmax);
if(rm >= cmin) {
res = (res + (rm - cmin + 1) * 4) % mod;
}
rm = min_denom(X / a[0] / a[1], R - a[0] - 1);
rm = max(rm, cmin);
if(rm <= cmax) {
res = (res + (cmax - rm + 1) * 4) % mod;
}
rm = min_denom(X / a[0] / a[1], R - a[1] - 1);
rm = max(rm, cmin);
if(rm <= cmax) {
res = (res + (cmax - rm + 1) * 4) % mod;
}
LL le = cmin, ri = cmax + 1;
while(le != ri) {
LL mid = (le + ri) / 2;
if(mid + X / a[0] / a[1] / mid < R) {
ri = mid;
}else {
le = mid + 1;
}
}
res = (res + (cmax - le + 1) * 4) % mod;
}else {
assert(false);
if(a[0] + a[1] < R) {
res = (res + (cmax - cmin + 1) * 2) % mod;
}
LL rm = R - a[0] - 1;
rm = min(rm, cmax);
if(rm >= cmin) {
res = (res + (rm - cmin + 1) * 4) % mod;
}
//cout << "rm = " << rm << ' ' << res << endl;
rm = min_denom(X / a[0] / a[1], R - a[0] - 1);
cout << X / a[0] / a[1] << '?' << R - a[0] - 1 << '?' << rm << endl;
rm = max(rm, cmin);
if(rm <= cmax) {
res = (res + (cmax - rm + 1) * 4) % mod;
}
//cout << "rm = " << rm << ' ' << res << endl;
LL le = cmin, ri = cmax + 1;
while(le != ri) {
LL mid = (le + ri) / 2;
if(mid + X / a[0] / a[1] / mid < R) {
ri = mid;
}else {
le = mid + 1;
}
}
///cout << "le = " << le << ' ' << res << endl;
res = (res + (cmax - le + 1) * 2) % mod;
}
}
}
//cout << "res = " << res << endl;
if(false) {
int rr = 0;
for(a[0] = 1; a[0] <= X; a[0]++) {
for(a[1] = 1; a[1] <= X; a[1]++) {
for(a[2] = 1; a[2] <= X; a[2]++) {
for(a[3] = 1; a[3] <= X; a[3]++) {
if(a[0] * a[1] * a[2] * a[3] <= X &&
(a[0] + 1) * a[1] * a[2] * a[3] > X &&
(a[0] + 0) * (a[1] + 1) * a[2] * a[3] > X &&
(a[0] + 0) * (a[1] + 0) * (a[2] + 1) * a[3] > X &&
(a[0] + 0) * (a[1] + 0) * (a[2] + 0) * (a[3] + 1) > X &&
a[0] + a[1] < 6 && a[0] + a[1] >= 5) {
printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
rr++;
}
}
}
}
}
cout << rr << "vs " << res << endl;
}
return res;
}
int main() {
LL X, L, R;
cin >> X >> L >> R;
cout << ((calc(X, R) - calc(X, L) + mod)) % mod << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1061ms
memory: 3516kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1041ms
memory: 3632kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 952ms
memory: 3556kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 965ms
memory: 3640kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 978ms
memory: 3568kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 1016ms
memory: 3512kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 1015ms
memory: 3556kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 970ms
memory: 3556kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 1016ms
memory: 3636kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 986ms
memory: 3628kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 1045ms
memory: 3636kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 1076ms
memory: 3636kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 1071ms
memory: 3708kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 1028ms
memory: 3700kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 1079ms
memory: 3516kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 1016ms
memory: 3636kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 987ms
memory: 3632kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 978ms
memory: 3564kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 922ms
memory: 3556kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 1037ms
memory: 3560kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 1078ms
memory: 3632kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 1010ms
memory: 3544kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 1111ms
memory: 3536kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'