QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211484 | #5477. Cake Decoration | bulijiojiodibuliduo# | AC ✓ | 375ms | 4128kb | C++17 | 2.7kb | 2023-10-12 17:09:02 | 2023-10-12 17:09:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
ll X,L,R;
ll ans=0;
ll dsqrt(ll x) {
ll y=sqrt(x)+0.1;
while (y*y>x) --y;
return y;
}
ll calc(ll X,ll R) {
ll ans=0;
auto num=[&](ll l,ll r) {
return l<=r?r-l+1:0ll;
};
auto cd=[&](ll a,ll b) {
return (a+b-1)/b;
};
for (ll a=1;a*(a+1)*(a+2)*(a+3)<=X;a++) {
for (ll b=a+1;a*b*(b+1)*(b+2)<=X;b++) {
ll x=X/a/b;
ll lc=b+1,rc=(dsqrt(4*x+1)-1)/2;
if (a+b<=R) ans+=rc-lc+1;
ans+=num(lc,min(R-a,rc));
ans+=num(lc,min(R-b,rc));
if (a+rc+1<=R) {
ans+=num(max(lc,x/(R-a+1)+1),rc);
}
if (b+rc+1<=R) {
ans+=num(max(lc,x/(R-b+1)+1),rc);
}
if (rc+x/rc<=R) {
if (lc+x/lc<=R) ans+=rc-lc+1;
else {
ll l=lc,r=rc;
while (l+1<r) {
ll md=(l+r)/2;
if (md+x/md<=R) r=md; else l=md;
}
ans+=rc-r+1;
}
}
}
}
//printf("!! %lld\n",ans*4);
return ans*4;
}
/*ll calc2(ll X,ll R) {
ll ans=0;
for (ll a=1;a*(a+1)*(a+2)*(a+3)<=X;a++) {
for (ll b=a+1;a*b*(b+1)*(b+2)<=X;b++) {
for (ll c=b+1;a*b*c*(c+1)<=X;c++) {
ll d=X/a/b/c;
if (a+b<=R) ans++;
if (a+c<=R) ans++;
if (a+d<=R) ans++;
if (b+c<=R) ans++;
if (b+d<=R) ans++;
if (c+d<=R) ans++;
}
}
}
return ans*4;
}*/
int main() {
scanf("%lld%lld%lld",&X,&L,&R);
ans=calc(X,R-1)-calc(X,L-1);
/*assert(calc(100000000000ll,1)==calc2(100000000000ll,1));
assert(calc(100000000000ll,12)==calc2(100000000000ll,12));
assert(calc(100000000000ll,123)==calc2(100000000000ll,123));
assert(calc(100000000000ll,1234)==calc2(100000000000ll,1234));
assert(calc(100000000000ll,12345)==calc2(100000000000ll,12345));
assert(calc(100000000000ll,123456)==calc2(100000000000ll,123456));
assert(calc(100000000000ll,1234567)==calc2(100000000000ll,1234567));
assert(calc(100000000000ll,12345678)==calc2(100000000000ll,12345678));
assert(calc(100000000000ll,123456789)==calc2(100000000000ll,123456789));
assert(calc(100000000000ll,1234567890)==calc2(100000000000ll,1234567890));*/
printf("%lld\n",ans%998244353);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3816kb
input:
24 4 6
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
30 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
30 9 20
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 264ms
memory: 3844kb
input:
100000000000000 1 100000000000000
output:
288287412
result:
ok single line: '288287412'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
51256 4 35
output:
29116
result:
ok single line: '29116'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
5845 10 163
output:
10724
result:
ok single line: '10724'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
47139 6 167
output:
71716
result:
ok single line: '71716'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
20603 5 167
output:
36556
result:
ok single line: '36556'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
37521 1 76
output:
46956
result:
ok single line: '46956'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 1 10
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 257ms
memory: 3832kb
input:
97083668416826 7 3808058212682
output:
392082021
result:
ok single line: '392082021'
Test #12:
score: 0
Accepted
time: 241ms
memory: 3796kb
input:
81206220725808 2 45630676823009
output:
956896057
result:
ok single line: '956896057'
Test #13:
score: 0
Accepted
time: 241ms
memory: 3776kb
input:
83357713762616 8 7064282922851
output:
238276229
result:
ok single line: '238276229'
Test #14:
score: 0
Accepted
time: 247ms
memory: 4128kb
input:
85445471832361 6 56105073865950
output:
611528255
result:
ok single line: '611528255'
Test #15:
score: 0
Accepted
time: 253ms
memory: 3824kb
input:
92699451513867 7 40224031632009
output:
527678799
result:
ok single line: '527678799'
Test #16:
score: 0
Accepted
time: 278ms
memory: 3836kb
input:
91239680645595 2 6753821
output:
949101816
result:
ok single line: '949101816'
Test #17:
score: 0
Accepted
time: 251ms
memory: 3796kb
input:
84407166448013 9 9804427
output:
100140616
result:
ok single line: '100140616'
Test #18:
score: 0
Accepted
time: 261ms
memory: 3812kb
input:
92300784798569 1 7627255
output:
506797132
result:
ok single line: '506797132'
Test #19:
score: 0
Accepted
time: 251ms
memory: 4124kb
input:
86360099055961 16 9430857
output:
909028853
result:
ok single line: '909028853'
Test #20:
score: 0
Accepted
time: 270ms
memory: 4084kb
input:
96378494166704 16 4791452
output:
961637838
result:
ok single line: '961637838'
Test #21:
score: 0
Accepted
time: 369ms
memory: 3832kb
input:
92800119725342 19 71735
output:
549693103
result:
ok single line: '549693103'
Test #22:
score: 0
Accepted
time: 302ms
memory: 3788kb
input:
99241248175798 28 509556
output:
885647806
result:
ok single line: '885647806'
Test #23:
score: 0
Accepted
time: 304ms
memory: 4120kb
input:
90117794770692 17 324480
output:
701148580
result:
ok single line: '701148580'
Test #24:
score: 0
Accepted
time: 322ms
memory: 3844kb
input:
99417213318477 67 305057
output:
478902343
result:
ok single line: '478902343'
Test #25:
score: 0
Accepted
time: 275ms
memory: 4124kb
input:
90584131165693 78 897660
output:
879735139
result:
ok single line: '879735139'
Test #26:
score: 0
Accepted
time: 179ms
memory: 3756kb
input:
92129120236843 702 5645
output:
28323443
result:
ok single line: '28323443'
Test #27:
score: 0
Accepted
time: 179ms
memory: 3888kb
input:
90203225783100 802 6272
output:
966952096
result:
ok single line: '966952096'
Test #28:
score: 0
Accepted
time: 162ms
memory: 3824kb
input:
82248112022135 533 2266
output:
280479804
result:
ok single line: '280479804'
Test #29:
score: 0
Accepted
time: 374ms
memory: 3888kb
input:
84853900427215 368 25431
output:
471070321
result:
ok single line: '471070321'
Test #30:
score: 0
Accepted
time: 375ms
memory: 3820kb
input:
91754392379969 149 24312
output:
577285220
result:
ok single line: '577285220'
Test #31:
score: 0
Accepted
time: 178ms
memory: 4088kb
input:
100000000000000 1 2
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 349ms
memory: 4120kb
input:
100000000000000 10000000000000 100000000000000
output:
36
result:
ok single line: '36'