QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #579548 | #5477. Cake Decoration | mrkiencf# | AC ✓ | 2381ms | 3736kb | C++14 | 4.3kb | 2024-09-21 15:06:19 | 2024-09-21 15:06:20 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int O = 1e6 + 50;
const int mod = 998244353;
int X, L, R, dem;
void Add(int &x, int y){
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
int sqr4(int x){
return x * x * x * x;
}
int sqr3(int x){
return x * x * x;
}
bool check(int x){
return L <= x && x <= R;
}
main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
X = L = R = 1e14;
cin >> X >> L >> R; R -= 1;
int cnt = 0;
/*for (int i = 1; i <= X; ++ i){
for (int j = i + 1; j <= X; ++ j){
for (int z = j + 1; z <= X; ++ z){
for (int l = z + 1; l <= X; ++ l){
int x = i * z * j;
if (x * l <= X && x * (l + 1) > X){
cnt += check(i + j);
cnt += check(i + l);
cnt += check(i + z);
cnt += check(j + l);
cnt += check(j + z);
cnt += check(z + l);
//if (check(i + j)) cout << i << " " << j
}
}
}
}
}*/
//cout << cnt * 4 << " ";
for (int i = 1; i * (i + 1) * (i + 2) * (i + 3) <= X; ++ i){
int Y = X / i;
for (int j = i + 1; i * j * (j + 1) * (j + 2) <= X; ++ j){
int Z = Y / j;
int minZ = j + 1;
int maxZ = sqrt(Z);
maxZ -= ((Z / maxZ) == maxZ);
if (minZ > maxZ) break;
int minL = Z / maxZ;
int maxL = Z / minZ;
if (minL > maxL) continue;
/// i j
Add(dem, (maxZ - minZ + 1) * check(i + j) % mod);
/// i z
if (i <= R) Add(dem, max(0ll, min(maxZ, R - i) - max(L - i, minZ) + 1));
/// j z
if (j <= R) Add(dem, max(0ll, min(maxZ, R - j) - max(L - j, minZ) + 1));
/// i l
if (i <= R){
int l = minZ, r = maxZ;
while (l <= r){
int mid = (l + r) / 2;
if (Z / mid > R - i) l = mid + 1;
else r = mid - 1;
}
// l
int rig = max(minZ, l);
l = minZ; r = maxZ;
while (l <= r){
int mid = (l + r) / 2;
if (Z / mid >= L - i) l = mid + 1;
else r = mid - 1;
}
// r
r = min(maxZ, r);
Add(dem, max(0ll, r - rig + 1));
//cout << "i l " << max(0ll, r - rig + 1) << endl;
}
/// j l
if (j <= R){
int l = minZ, r = maxZ;
while (l <= r){
int mid = (l + r) / 2;
if (Z / mid > R - j) l = mid + 1;
else r = mid - 1;
}
// l
int rig = max(minZ, l);
//cout << rig << " ";
l = minZ; r = maxZ;
while (l <= r){
int mid = (l + r) / 2;
if (Z / mid >= L - j) l = mid + 1;
else r = mid - 1;
}
// r
r = min(maxZ, r);
Add(dem, max(0ll, r - rig + 1));
//cout << "j l " << max(0ll, r - rig + 1) << endl;
}
/// z l
{
int l = minZ, r = maxZ;
while (l <= r){
int mid = (l + r) / 2;
if (Z / mid + mid > R) l = mid + 1;
else r = mid - 1;
}
// l
int rig = max(minZ, l);
l = minZ; r = maxZ;
while (l <= r){
int mid = (l + r) / 2;
if (Z / mid + mid < L) r = mid - 1;
else l = mid + 1;
}
// r
r = min(maxZ, r);
Add(dem, max(0ll, r - rig + 1));
}
}
}
cout << (dem * 4) % mod;
}
/***
***/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2215ms
memory: 3692kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 2182ms
memory: 3512kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 1981ms
memory: 3560kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 2008ms
memory: 3696kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 2035ms
memory: 3604kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 2128ms
memory: 3684kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 2119ms
memory: 3660kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 2033ms
memory: 3692kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 2131ms
memory: 3548kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 2056ms
memory: 3516kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 2184ms
memory: 3664kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 2311ms
memory: 3628kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 2262ms
memory: 3612kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 2168ms
memory: 3552kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 2283ms
memory: 3628kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 2138ms
memory: 3688kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 2108ms
memory: 3736kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 2128ms
memory: 3628kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 1628ms
memory: 3508kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 2281ms
memory: 3564kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 2381ms
memory: 3608kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 912ms
memory: 3544kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 2123ms
memory: 3660kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'