QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#171268#5477. Cake DecorationPhantomThreshold#AC ✓2591ms3720kbC++201.7kb2023-09-09 16:42:592023-09-09 16:42:59

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 16:42:59]
  • 评测
  • 测评结果:AC
  • 用时:2591ms
  • 内存:3720kb
  • [2023-09-09 16:42:59]
  • 提交

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'