QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152202 | #5477. Cake Decoration | nathanlee726 | AC ✓ | 1113ms | 3812kb | C++17 | 2.5kb | 2023-08-27 18:30:01 | 2023-08-27 18:30:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T> void pv(T a, T b) {
for (T i = a; i != b; ++i) cerr << *i << " ";
cerr << endl;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
// maroon shakyou-modint
using ll=long long;
const uint mod=998244353;
struct mint{
uint v;
mint(ll vv=0){s(vv%mod+mod);}
mint& s(uint vv){
v=vv<mod?vv:vv-mod;
return *this;
}
mint operator-()const{return mint()-*this;}
mint&operator+=(mint r){return s(v+r.v);}
mint&operator-=(mint r){return s(v+mod-r.v);}
mint&operator*=(mint r){v=(unsigned ll)v*r.v%mod;return *this;}
mint&operator/=(mint r){return *this*=r.inv();}
mint operator+(mint r)const{return mint(*this)+=r;}
mint operator-(mint r)const{return mint(*this)-=r;}
mint operator*(mint r)const{return mint(*this)*=r;}
mint operator/(mint r)const{return mint(*this)/=r;}
mint pow(ll n)const{
if(n<0)return inv().pow(-n);
mint res(1),x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
mint inv()const{return pow(mod-2);}
};
ostream &operator<<(ostream &os, mint a) {
return os << a.v;
}
mint solve(const Int X, const Int R) {
mint ans = 0;
for (Int a = 1; a*(a+1)*(a+2)*(a+3) <= X; ++a) {
for (Int b = a + 1; a * b*(b+1)*(b+2) <= X; ++b) {
const Int y = X / (a * b);
Int lb = b + 1;
Int ub = sqrt((long double)y);
for (; ub * (ub + 1) > y; --ub) {}
auto add = [&](Int c0, Int c1) -> void {
// if(X<=30)cerr<<a<<" "<<b<<": ["<<c0<<", "<<c1<<"]"<<endl;
if (c0 <= c1) {
ans += (c1 - c0 + 1);
}
};
// a+b
if (a + b < R) add(lb, ub);
// a+c, b+c
add(lb, min(ub, R - a - 1));
add(lb, min(ub, R - b - 1));
// a+d, b+d
if (R - a > 0) add(max(lb, y / (R - a) + 1), ub);
if (R - b > 0) add(max(lb, y / (R - b) + 1), ub);
// c+d
Int lo = lb - 1, hi = ub + 1;
for (; lo + 1 < hi; ) {
const Int mid = (lo + hi) / 2;
((mid + y / mid < R) ? hi : lo) = mid;
}
add(hi, ub);
}
}
return ans;
}
int main() {
Int X, L, R;
for (; ~scanf("%lld%lld%lld", &X, &L, &R); ) {
mint ans = 0;
ans += solve(X, R);
ans -= solve(X, L);
ans *= 4;
printf("%u\n", ans.v);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 1ms
memory: 3588kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1070ms
memory: 3764kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1050ms
memory: 3604kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 961ms
memory: 3632kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 974ms
memory: 3584kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 990ms
memory: 3604kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 1029ms
memory: 3580kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 1021ms
memory: 3696kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 983ms
memory: 3704kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 1031ms
memory: 3704kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 995ms
memory: 3804kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 1055ms
memory: 3576kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 1098ms
memory: 3616kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 1088ms
memory: 3796kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 1042ms
memory: 3584kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 1094ms
memory: 3580kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 1027ms
memory: 3808kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 1033ms
memory: 3812kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 1025ms
memory: 3764kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 967ms
memory: 3580kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 1066ms
memory: 3588kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 1113ms
memory: 3804kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 1060ms
memory: 3640kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 1081ms
memory: 3612kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'