QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173745#5477. Cake DecorationForever_Young#AC ✓1111ms3716kbC++143.8kb2023-09-10 01:36:222023-09-10 01:36:22

Judging History

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

  • [2023-09-10 01:36:22]
  • 评测
  • 测评结果:AC
  • 用时:1111ms
  • 内存:3716kb
  • [2023-09-10 01:36:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
typedef long long LL;
const LL mod = 998244353;
LL a[4], b[4];
inline LL min_denom(LL a, LL c) {
	return c >= 0 ? a / (c + 1) + 1 : mod * mod;
}
inline LL intsq(LL x) {
	LL res = LL(sqrt(x));
	while(res * res > x) {
		res--;
	}
	while((res + 1) * (res + 1) <= x) {
		res++;
	}
	return res;
}
LL calc(LL X, LL R) {
	LL res = 0;
	auto calc = [&]() {
		memcpy(b, a, sizeof(b));
		do {
			if(b[0] + b[1] < R) {
				res++;
			}
		} while(next_permutation(b, b + 4)); 
		res %= mod;
	};
	for(a[0] = 1; a[0] <= 3162; a[0]++) {
		//cout << a[0] << endl;
		for(a[1] = a[0] + 1; a[0] * a[1] * a[1] * a[1] <= X; a[1]++) {

			//cout << a[0] << ' ' << a[1] << ':' << res << endl;
			LL cmin = a[1] + 1, cmax = intsq(X / a[0] / a[1]);
			//cout << cmin << '?' << cmax << endl;
			if(cmax == X / a[0] / a[1] / cmax) {
				cmax--;
			}
			if(cmin > cmax) continue;
			/*a[2] = cmin;
			a[3] = X / a[0] / a[1] / a[2];
			calc();
			if(cmax > cmin) {
				a[2] = cmax;
				a[3] = X / a[0] / a[1] / a[2];
				calc();
			}
			cmin++;
			cmax--;
			if(cmin > cmax) continue;*/
			if(a[0] != a[1]) {
				if(a[0] + a[1] < R) {
					res = (res + (cmax - cmin + 1) * 4) % mod;
				}
				LL rm = R - a[0] - 1;
				rm = min(rm, cmax);
				if(rm >= cmin) {
					res = (res + (rm - cmin + 1) * 4) % mod;
				}
				rm = R - a[1] - 1;
				rm = min(rm, cmax);
				if(rm >= cmin) {
					res = (res + (rm - cmin + 1) * 4) % mod;
				}
				rm = min_denom(X / a[0] / a[1], R - a[0] - 1);
				rm = max(rm, cmin);
				if(rm <= cmax) {
					res = (res + (cmax - rm + 1) * 4) % mod;
				}
				rm = min_denom(X / a[0] / a[1], R - a[1] - 1);
				rm = max(rm, cmin);
				if(rm <= cmax) {
					res = (res + (cmax - rm + 1) * 4) % mod;
				}
				LL le = cmin, ri = cmax + 1;
				while(le != ri) {
					LL mid = (le + ri) / 2;
					if(mid + X / a[0] / a[1] / mid < R) {
						ri = mid;
					}else {
						le = mid + 1;
					}
				}
				res = (res + (cmax - le + 1) * 4) % mod;
			}else {
				assert(false);
				if(a[0] + a[1] < R) {
					res = (res + (cmax - cmin + 1) * 2) % mod;
				}
				LL rm = R - a[0] - 1;
				rm = min(rm, cmax);
				if(rm >= cmin) {
					res = (res + (rm - cmin + 1) * 4) % mod;
				}
				//cout << "rm = " << rm << ' ' << res << endl;
				
				rm = min_denom(X / a[0] / a[1], R - a[0] - 1);
				cout << X / a[0] / a[1] << '?' << R - a[0] - 1 << '?' << rm << endl;
				rm = max(rm, cmin);
				if(rm <= cmax) {
					res = (res + (cmax - rm + 1) * 4) % mod;
				}
				//cout << "rm = " << rm << ' ' << res << endl;
				
				LL le = cmin, ri = cmax + 1;
				while(le != ri) {
					LL mid = (le + ri) / 2;
					if(mid + X / a[0] / a[1] / mid < R) {
						ri = mid;
					}else {
						le = mid + 1;
					}
				}
				///cout << "le = " << le << ' ' << res << endl;
				res = (res + (cmax - le + 1) * 2) % mod;
			}
		}
	}
	//cout << "res = " << res << endl;

	if(false) {
		int rr = 0;
		for(a[0] = 1; a[0] <= X; a[0]++) {
		for(a[1] = 1; a[1] <= X; a[1]++) {
		for(a[2] = 1; a[2] <= X; a[2]++) {
		for(a[3] = 1; a[3] <= X; a[3]++) {
			if(a[0] * a[1] * a[2] * a[3] <= X && 
			(a[0] + 1) * a[1] * a[2] * a[3] > X && 
			(a[0] + 0) * (a[1] + 1) * a[2] * a[3] > X && 
			(a[0] + 0) * (a[1] + 0) * (a[2] + 1) * a[3] > X && 
			(a[0] + 0) * (a[1] + 0) * (a[2] + 0) * (a[3] + 1) > X && 
			a[0] + a[1] < 6 && a[0] + a[1] >= 5) {
				printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
				rr++;
			}
		}
		}
		}
		}
		cout << rr << "vs " << res << endl;
	}
	return res;
}
int main() {
	LL X, L, R;
	cin >> X >> L >> R;
	cout << ((calc(X, R) - calc(X, L) + mod)) % mod << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

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: 0ms
memory: 3648kb

input:

30 9 20

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1061ms
memory: 3516kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

51256 4 35

output:

29116

result:

ok single line: '29116'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

5845 10 163

output:

10724

result:

ok single line: '10724'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

47139 6 167

output:

71716

result:

ok single line: '71716'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

20603 5 167

output:

36556

result:

ok single line: '36556'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

37521 1 76

output:

46956

result:

ok single line: '46956'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

1 1 10

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1041ms
memory: 3632kb

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

score: 0
Accepted
time: 952ms
memory: 3556kb

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

score: 0
Accepted
time: 965ms
memory: 3640kb

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

score: 0
Accepted
time: 978ms
memory: 3568kb

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

score: 0
Accepted
time: 1016ms
memory: 3512kb

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

score: 0
Accepted
time: 1015ms
memory: 3556kb

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

score: 0
Accepted
time: 970ms
memory: 3556kb

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

score: 0
Accepted
time: 1016ms
memory: 3636kb

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0
Accepted
time: 986ms
memory: 3628kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

score: 0
Accepted
time: 1045ms
memory: 3636kb

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

score: 0
Accepted
time: 1076ms
memory: 3636kb

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

score: 0
Accepted
time: 1071ms
memory: 3708kb

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

score: 0
Accepted
time: 1028ms
memory: 3700kb

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

score: 0
Accepted
time: 1079ms
memory: 3516kb

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

score: 0
Accepted
time: 1016ms
memory: 3636kb

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

score: 0
Accepted
time: 987ms
memory: 3632kb

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

score: 0
Accepted
time: 978ms
memory: 3564kb

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

score: 0
Accepted
time: 922ms
memory: 3556kb

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

score: 0
Accepted
time: 1037ms
memory: 3560kb

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0
Accepted
time: 1078ms
memory: 3632kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

score: 0
Accepted
time: 1010ms
memory: 3544kb

input:

100000000000000 1 2

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 1111ms
memory: 3536kb

input:

100000000000000 10000000000000 100000000000000

output:

36

result:

ok single line: '36'