QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211484#5477. Cake Decorationbulijiojiodibuliduo#AC ✓375ms4128kbC++172.7kb2023-10-12 17:09:022023-10-12 17:09:03

Judging History

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

  • [2023-10-12 17:09:03]
  • 评测
  • 测评结果:AC
  • 用时:375ms
  • 内存:4128kb
  • [2023-10-12 17:09:02]
  • 提交

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'