QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190733 | #5477. Cake Decoration | w4p3r | AC ✓ | 2591ms | 3500kb | C++20 | 2.5kb | 2023-09-29 13:36:32 | 2023-09-29 13:36:32 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define REP(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
char ch = getchar();
ll s = 0, w = 1;
while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
#define int ll
const int mod = 998244353;
int x, l, r;
int ans;
bool ck(const int x) {return (l <= x && x < r);}
int calc(int L, int R, int n)
{
if (L > n)return 0;
return min(n, R) - L + 1;
}
int sol(int R)
{
int sum = 0;
for (int a = 1;; a ++)
{
if (a * a * a * a > x)break;
for (int b = a + 1;; b ++)
{
if (a * b * b * b > x)break;
int tx = x / a / b;
int lc = b + 1, rc = sqrt(tx);
while(rc >= tx / rc)rc --;
if (lc > rc)continue;
// cout << "GG:" << a << ' ' << b << ' ' << lc << ' ' << rc << endl;
if (a + b <= R)sum = (sum + rc - lc + 1) % mod; // ab
// cout << "EE:" << sum << endl;
sum = (sum + calc(a + lc, a + rc, R)) % mod; // ac
// cout << "EE:" << sum << endl;
int ql, qr, pos;
ql = lc, qr = rc, pos = rc + 1;
while (ql <= qr)
{
int mid = (ql + qr) >> 1;
if (tx / mid + a <= R)pos = mid, qr = mid - 1;
else ql = mid + 1;
}
sum = (sum + rc - pos + 1) % mod; // ad
// cout << "EE:" << sum << endl;
sum = (sum + calc(b + lc, b + rc, R)) % mod;// bc
// cout << "EE:" << sum << endl;
ql = lc, qr = rc, pos = rc + 1;
while (ql <= qr)
{
int mid = (ql + qr) >> 1;
if (tx / mid + b <= R)pos = mid, qr = mid - 1;
else ql = mid + 1;
}
sum = (sum + rc - pos + 1) % mod; // bd
// cout << "EE:" << sum << endl;
ql = lc, qr = rc, pos = rc + 1;
while (ql <= qr)
{
int mid = (ql + qr) >> 1;
assert(mid < rc || tx / mid + mid >= tx / (mid + 1) + (mid + 1));
if (tx / mid + mid <= R)pos = mid, qr = mid - 1;
else ql = mid + 1;
}
sum = (sum + rc - pos + 1) % mod; // cd
// cout << "EE:" << sum << endl;
}
}
return sum;
}
signed main()
{
// freopen("C.in", "r", stdin);
// freopen("C.out", "w", stdout);
x = read(), l = read(), r = read();
// cerr << sol(r - 1) << ' ' << sol(l - 1) << endl;
cout << 4LL * (sol(r - 1) + mod - sol(l - 1)) % mod << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3464kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3332kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2400ms
memory: 3360kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3344kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 2363ms
memory: 3220kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 2152ms
memory: 3352kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 2177ms
memory: 3464kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 2211ms
memory: 3340kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 2307ms
memory: 3404kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 2309ms
memory: 3392kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 2203ms
memory: 3480kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 2311ms
memory: 3352kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 2225ms
memory: 3336kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 2367ms
memory: 3336kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 2498ms
memory: 3356kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 2449ms
memory: 3404kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 2346ms
memory: 3216kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 2474ms
memory: 3388kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 2316ms
memory: 3348kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 2418ms
memory: 3336kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 2438ms
memory: 3388kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 2273ms
memory: 3396kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 2485ms
memory: 3348kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 2591ms
memory: 3344kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 2518ms
memory: 3500kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 2279ms
memory: 3340kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'