QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103133#5477. Cake Decoration8BQube#AC ✓3983ms3524kbC++173.7kb2023-05-04 16:13:302023-05-04 16:13:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-04 16:13:33]
  • 评测
  • 测评结果:AC
  • 用时:3983ms
  • 内存:3524kb
  • [2023-05-04 16:13:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

const int MOD = 998244353;
const ll INF = 9e18;

ll lgap(ll a, ll x) { // a / b < x, b >= ?
    if (x <= 0) return INF;
    return a / x + 1;
}

ll rgap(ll a, ll x) { // a / b >= x, b <= ?
    if (x <= 0) return INF;
    return a / x;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ll x, l, r;
    cin >> x >> l >> r;
    //ll cnt = 0, cnt2 = 0;
    ll ans = 0;
    for (ll a = 1; a * (a + 1) * (a + 2) * (a + 3) <= x; ++a) {
        ll xa = x / a;
        for (ll b = a + 1; a * b * (b + 1) * (b + 2) <= x; ++b) {
            ll xab = xa / b;
            ll s = sqrt(xab);
            while (s * s < xab) ++s;
            while (s >= xab / s) --s;
            //cnt += max(0LL, s - b);
            //++cnt2;

            //cerr << a << " " << b << " *****\n";

            // a + b
            if (l <= a + b && a + b < r) {
                ans += (s - b) * 4;
                /*cerr << "Case 1\n";
                for (ll i = b + 1; i <= s; ++i)
                    cerr << i << " " << xab / i << "\n";*/
            }

            // a + c
            {
                ll lft = max(b + 1, l - a);
                ll rgt = min(s, r - a - 1);
                ans += max(0LL, rgt - lft + 1) * 4;
                /*cerr << "Case 2\n";
                for (ll i = lft; i <= rgt; ++i)
                    cerr << i << " " << xab / i << "\n";*/
            }

            // b + c
            {
                ll lft = max(b + 1, l - b);
                ll rgt = min(s, r - b - 1);
                ans += max(0LL, rgt - lft + 1) * 4;
                /*cerr << "Case 3\n";
                for (ll i = lft; i <= rgt; ++i)
                    cerr << i << " " << xab / i << "\n";*/
            }

            // a + d
            {
                ll lft = max(lgap(xab, r - a), b + 1);
                ll rgt = min(rgap(xab, l - a), s);
                ans += max(0LL, rgt - lft + 1) * 4;
                /*cerr << "Case 4\n";
                for (ll i = lft; i <= rgt; ++i)
                    cerr << i << " " << xab / i << "\n";*/
            }

            // b + d
            {
                ll lft = max(lgap(xab, r - b), b + 1);
                ll rgt = min(rgap(xab, l - a), s);
                ans += max(0LL, rgt - lft + 1) * 4;
                /*cerr << "Case 5\n";
                for (ll i = lft; i <= rgt; ++i)
                    cerr << i << " " << xab / i << "\n";*/
            }

            // c + d
            {
                ll lft, rgt;

                if ((b + 1) + xab / (b + 1) < l) rgt = b;
                else {
                    ll p = b + 1, q = s + 1;
                    while (q - p > 1) {
                        ll mid = (p + q) / 2;
                        if (mid + xab / mid >= l) p = mid;
                        else q = mid;
                    }
                    rgt = p;
                }

                if (s + xab / s >= r) lft = s + 1;
                else {
                    ll p = b, q = s;
                    while (q - p > 1) {
                        ll mid = (p + q) / 2;
                        if (mid + xab / mid < r) q = mid;
                        else p = mid;
                    }
                    lft = q;
                }

                ans += max(0LL, rgt - lft + 1) * 4;
                /*cerr << "Case 6\n";
                for (ll i = lft; i <= rgt; ++i)
                    cerr << i << " " << xab / i << "\n";*/
            }
        }
    }
    //cout << cnt << "\n"; // 76377704980
    //cout << cnt2 << "\n"; // 9950107 

    cout << ans % MOD << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3456kb

input:

24 4 6

output:

12

result:

ok single line: '12'

Test #2:

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

input:

30 5 6

output:

4

result:

ok single line: '4'

Test #3:

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

input:

30 9 20

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 3945ms
memory: 3468kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3260kb

input:

51256 4 35

output:

29116

result:

ok single line: '29116'

Test #6:

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

input:

5845 10 163

output:

10724

result:

ok single line: '10724'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3452kb

input:

47139 6 167

output:

71716

result:

ok single line: '71716'

Test #8:

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

input:

20603 5 167

output:

36556

result:

ok single line: '36556'

Test #9:

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

input:

37521 1 76

output:

46956

result:

ok single line: '46956'

Test #10:

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

input:

1 1 10

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 3883ms
memory: 3508kb

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

score: 0
Accepted
time: 3532ms
memory: 3328kb

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

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

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

score: 0
Accepted
time: 3627ms
memory: 3308kb

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

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

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

score: 0
Accepted
time: 3755ms
memory: 3256kb

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

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

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

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

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0
Accepted
time: 3653ms
memory: 3364kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

score: 0
Accepted
time: 3875ms
memory: 3312kb

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

score: 0
Accepted
time: 3730ms
memory: 3524kb

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

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

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

score: 0
Accepted
time: 3746ms
memory: 3452kb

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

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

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

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

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

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

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

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

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

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

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

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

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0
Accepted
time: 3373ms
memory: 3308kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

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

input:

100000000000000 1 2

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 2308ms
memory: 3468kb

input:

100000000000000 10000000000000 100000000000000

output:

36

result:

ok single line: '36'