QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103133 | #5477. Cake Decoration | 8BQube# | AC ✓ | 3983ms | 3524kb | C++17 | 3.7kb | 2023-05-04 16:13:30 | 2023-05-04 16:13:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
const int MOD = 998244353;
const ll INF = 9e18;
ll lgap(ll a, ll x) { // a / b < x, b >= ?
if (x <= 0) return INF;
return a / x + 1;
}
ll rgap(ll a, ll x) { // a / b >= x, b <= ?
if (x <= 0) return INF;
return a / x;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
ll x, l, r;
cin >> x >> l >> r;
//ll cnt = 0, cnt2 = 0;
ll ans = 0;
for (ll a = 1; a * (a + 1) * (a + 2) * (a + 3) <= x; ++a) {
ll xa = x / a;
for (ll b = a + 1; a * b * (b + 1) * (b + 2) <= x; ++b) {
ll xab = xa / b;
ll s = sqrt(xab);
while (s * s < xab) ++s;
while (s >= xab / s) --s;
//cnt += max(0LL, s - b);
//++cnt2;
//cerr << a << " " << b << " *****\n";
// a + b
if (l <= a + b && a + b < r) {
ans += (s - b) * 4;
/*cerr << "Case 1\n";
for (ll i = b + 1; i <= s; ++i)
cerr << i << " " << xab / i << "\n";*/
}
// a + c
{
ll lft = max(b + 1, l - a);
ll rgt = min(s, r - a - 1);
ans += max(0LL, rgt - lft + 1) * 4;
/*cerr << "Case 2\n";
for (ll i = lft; i <= rgt; ++i)
cerr << i << " " << xab / i << "\n";*/
}
// b + c
{
ll lft = max(b + 1, l - b);
ll rgt = min(s, r - b - 1);
ans += max(0LL, rgt - lft + 1) * 4;
/*cerr << "Case 3\n";
for (ll i = lft; i <= rgt; ++i)
cerr << i << " " << xab / i << "\n";*/
}
// a + d
{
ll lft = max(lgap(xab, r - a), b + 1);
ll rgt = min(rgap(xab, l - a), s);
ans += max(0LL, rgt - lft + 1) * 4;
/*cerr << "Case 4\n";
for (ll i = lft; i <= rgt; ++i)
cerr << i << " " << xab / i << "\n";*/
}
// b + d
{
ll lft = max(lgap(xab, r - b), b + 1);
ll rgt = min(rgap(xab, l - a), s);
ans += max(0LL, rgt - lft + 1) * 4;
/*cerr << "Case 5\n";
for (ll i = lft; i <= rgt; ++i)
cerr << i << " " << xab / i << "\n";*/
}
// c + d
{
ll lft, rgt;
if ((b + 1) + xab / (b + 1) < l) rgt = b;
else {
ll p = b + 1, q = s + 1;
while (q - p > 1) {
ll mid = (p + q) / 2;
if (mid + xab / mid >= l) p = mid;
else q = mid;
}
rgt = p;
}
if (s + xab / s >= r) lft = s + 1;
else {
ll p = b, q = s;
while (q - p > 1) {
ll mid = (p + q) / 2;
if (mid + xab / mid < r) q = mid;
else p = mid;
}
lft = q;
}
ans += max(0LL, rgt - lft + 1) * 4;
/*cerr << "Case 6\n";
for (ll i = lft; i <= rgt; ++i)
cerr << i << " " << xab / i << "\n";*/
}
}
}
//cout << cnt << "\n"; // 76377704980
//cout << cnt2 << "\n"; // 9950107
cout << ans % MOD << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3456kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3308kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 3945ms
memory: 3468kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3260kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3348kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3332kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 3883ms
memory: 3508kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 3532ms
memory: 3328kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 3596ms
memory: 3360kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 3627ms
memory: 3308kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 3791ms
memory: 3360kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 3755ms
memory: 3256kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 3604ms
memory: 3336kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 3783ms
memory: 3392kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 3653ms
memory: 3364kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 3875ms
memory: 3312kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 3730ms
memory: 3524kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 3951ms
memory: 3396kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 3746ms
memory: 3452kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 3983ms
memory: 3336kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 3761ms
memory: 3336kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 2346ms
memory: 3400kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 2302ms
memory: 3400kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 2137ms
memory: 3332kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 3284ms
memory: 3396kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 3373ms
memory: 3308kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 2240ms
memory: 3352kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 2308ms
memory: 3468kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'