QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#171268 | #5477. Cake Decoration | PhantomThreshold# | AC ✓ | 2591ms | 3720kb | C++20 | 1.7kb | 2023-09-09 16:42:59 | 2023-09-09 16:42:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
void add(ll &a,ll b){
// b%=mod;
a+=b;
if (a>=mod) a-=mod;
}
ll CNT=0;
ll X;
ll gao(ll lim){
ll ans=0;
for (ll b=1;b*(b+1)*(b+2)<=X;b++){
ll ed=X/b/(b+1)/(b+2);
ed=min(ed,b-1);
for (ll a=1;a<=ed;a++){
ll mx=X/a/b;
ll lc=b+1;
ll rc=sqrtl(mx);
for (;(rc+1)*(rc+2)<=mx;) rc++;
for (;rc*(rc+1)>mx;) rc--;
// cerr << "a,b,lc,rc : " << a << " " << b << " " << lc << " " << rc << endl;
if (lc>rc) continue;
// cerr << "a,b,lc,rc : " << a << " " << b << " " << lc << " " << rc << endl;
{
//ab
if (a+b<=lim) add(ans,rc-lc+1);
}
{
//ac
ll lt=lc;
ll rt=rc;
rt=min(rt,lim-a);
if (lt<=rt) add(ans,rt-lt+1);
}
{
//bc
ll lt=lc;
ll rt=rc;
rt=min(rt,lim-b);
if (lt<=rt) add(ans,rt-lt+1);
}
{
//ad
ll lo=lc,hi=rc;
if (mx/hi+a<=lim){
for (;lo<hi;){
ll mid=(lo+hi)/2;
if (mx/mid+a<=lim) hi=mid;
else lo=mid+1;
}
add(ans,rc-lo+1);
}
}
{
//bd
ll lo=lc,hi=rc;
if (mx/hi+b<=lim){
for (;lo<hi;){
ll mid=(lo+hi)/2;
if (mx/mid+b<=lim) hi=mid;
else lo=mid+1;
}
add(ans,rc-lo+1);
}
}
{
//cd
ll lo=lc,hi=rc;
if (mx/hi+hi<=lim){
for (;lo<hi;){
ll mid=(lo+hi)/2;
if (mx/mid+mid<=lim) hi=mid;
else lo=mid+1;
}
add(ans,rc-lo+1);
}
}
}
}
return ans;
}
int main(){
ll L,R;
cin >> X >> L >> R;
ll ans=(gao(R-1)-gao(L-1))*4;
ans=(ans%mod+mod)%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: 3652kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1459ms
memory: 3712kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1429ms
memory: 3652kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 1309ms
memory: 3580kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 1327ms
memory: 3572kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 1344ms
memory: 3656kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 1399ms
memory: 3700kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 1397ms
memory: 3656kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 1344ms
memory: 3700kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 1400ms
memory: 3624kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 1355ms
memory: 3696kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 1444ms
memory: 3720kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 1592ms
memory: 3640kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 1518ms
memory: 3640kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 1460ms
memory: 3704kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 1547ms
memory: 3640kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 1425ms
memory: 3628kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 336ms
memory: 3700kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 455ms
memory: 3640kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 290ms
memory: 3636kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 1481ms
memory: 3696kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 1531ms
memory: 3580kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 320ms
memory: 3704kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 2591ms
memory: 3636kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'