QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190733#5477. Cake Decorationw4p3rAC ✓2591ms3500kbC++202.5kb2023-09-29 13:36:322023-09-29 13:36:32

Judging History

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

  • [2023-09-29 13:36:32]
  • 评测
  • 测评结果:AC
  • 用时:2591ms
  • 内存:3500kb
  • [2023-09-29 13:36:32]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define REP(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define int ll
const int mod = 998244353;
int x, l, r;
int ans;
bool ck(const int x) {return (l <= x && x < r);}
int calc(int L, int R, int n)
{
	if (L > n)return 0;
	return min(n, R) - L + 1;
}
int sol(int R)
{
	int sum = 0;
	for (int a = 1;; a ++)
	{
		if (a * a * a * a > x)break;
		for (int b = a + 1;; b ++)
		{
			if (a * b * b * b > x)break;
			int tx = x / a / b;
			int lc = b + 1, rc = sqrt(tx);
			while(rc >= tx / rc)rc --;
			if (lc > rc)continue;
			// cout << "GG:" << a << ' ' << b << ' ' << lc << ' ' << rc << endl;
			if (a + b <= R)sum = (sum + rc - lc + 1) % mod; // ab
			// cout << "EE:" << sum << endl;
			sum = (sum + calc(a + lc, a + rc, R)) % mod; // ac
			// cout << "EE:" << sum << endl;

			int ql, qr, pos;
			ql = lc, qr = rc, pos = rc + 1;
			while (ql <= qr)
			{
				int mid = (ql + qr) >> 1;
				if (tx / mid + a <= R)pos = mid, qr = mid - 1;
				else ql = mid + 1;
			}
			sum = (sum + rc - pos + 1) % mod; // ad
			// cout << "EE:" << sum << endl;

			sum = (sum + calc(b + lc, b + rc, R)) % mod;// bc
			// cout << "EE:" << sum << endl;

			ql = lc, qr = rc, pos = rc + 1;
			while (ql <= qr)
			{
				int mid = (ql + qr) >> 1;
				if (tx / mid + b <= R)pos = mid, qr = mid - 1;
				else ql = mid + 1;
			}
			sum = (sum + rc - pos + 1) % mod; // bd
			// cout << "EE:" << sum << endl;

			ql = lc, qr = rc, pos = rc + 1;
			while (ql <= qr)
			{
				int mid = (ql + qr) >> 1;
				assert(mid < rc || tx / mid + mid >= tx / (mid + 1) + (mid + 1));
				if (tx / mid + mid <= R)pos = mid, qr = mid - 1;
				else ql = mid + 1;
			}
			sum = (sum + rc - pos + 1) % mod; // cd
			// cout << "EE:" << sum << endl;
		}
	}
	return sum;
}
signed main()
{
	// freopen("C.in", "r", stdin);
	// freopen("C.out", "w", stdout);
	x = read(), l = read(), r = read();
	// cerr << sol(r - 1) << ' ' << sol(l - 1) << endl;
	cout << 4LL * (sol(r - 1) + mod - sol(l - 1)) % mod << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

24 4 6

output:

12

result:

ok single line: '12'

Test #2:

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

input:

30 5 6

output:

4

result:

ok single line: '4'

Test #3:

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

input:

30 9 20

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 2400ms
memory: 3360kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

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

input:

51256 4 35

output:

29116

result:

ok single line: '29116'

Test #6:

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

input:

5845 10 163

output:

10724

result:

ok single line: '10724'

Test #7:

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

input:

47139 6 167

output:

71716

result:

ok single line: '71716'

Test #8:

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

input:

20603 5 167

output:

36556

result:

ok single line: '36556'

Test #9:

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

input:

37521 1 76

output:

46956

result:

ok single line: '46956'

Test #10:

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

input:

1 1 10

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 2363ms
memory: 3220kb

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

score: 0
Accepted
time: 2152ms
memory: 3352kb

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

score: 0
Accepted
time: 2177ms
memory: 3464kb

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

score: 0
Accepted
time: 2211ms
memory: 3340kb

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

score: 0
Accepted
time: 2307ms
memory: 3404kb

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

score: 0
Accepted
time: 2309ms
memory: 3392kb

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

score: 0
Accepted
time: 2203ms
memory: 3480kb

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

score: 0
Accepted
time: 2311ms
memory: 3352kb

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0
Accepted
time: 2225ms
memory: 3336kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

score: 0
Accepted
time: 2367ms
memory: 3336kb

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

score: 0
Accepted
time: 2498ms
memory: 3356kb

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

score: 0
Accepted
time: 2449ms
memory: 3404kb

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

score: 0
Accepted
time: 2346ms
memory: 3216kb

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

score: 0
Accepted
time: 2474ms
memory: 3388kb

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

score: 0
Accepted
time: 2316ms
memory: 3348kb

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

score: 0
Accepted
time: 2418ms
memory: 3336kb

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

score: 0
Accepted
time: 2438ms
memory: 3388kb

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

score: 0
Accepted
time: 2273ms
memory: 3396kb

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

score: 0
Accepted
time: 2485ms
memory: 3348kb

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0
Accepted
time: 2591ms
memory: 3344kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

score: 0
Accepted
time: 2518ms
memory: 3500kb

input:

100000000000000 1 2

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 2279ms
memory: 3340kb

input:

100000000000000 10000000000000 100000000000000

output:

36

result:

ok single line: '36'