QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#747051#5477. Cake Decorationquannguyen2009AC ✓4302ms3692kbC++233.9kb2024-11-14 16:15:112024-11-14 16:15:11

Judging History

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

  • [2024-11-14 16:15:11]
  • 评测
  • 测评结果：AC
  • 用时：4302ms
  • 内存：3692kb
查看
  • [2024-11-14 16:15:11]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=1e5+5, mod = 998244353, inf = 1e18;

int X, L, R;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> X >> L >> R; R--;

    int res = 0;
    int lo, hi, lc, rc, tmpl, tmpr, ans;
    for (int a=1; a*(a+1)*(a+2)*(a+3)<=X; a++) {
        for (int b=a+1; a*b*(b+1)*(b+2)<=X; b++) {
            int n = X/(a*b);

            // find lc, rc
            lc = b+1;
            lo = 0, hi = sqrt(n), ans = -1;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if (mid*(mid+1)<=n) {
                    ans = mid;
                    lo = mid+1;
                } else {
                    hi = mid-1;
                }
            }
            rc = ans;
            if(lc>rc) continue;


            //L<=a+b<=R
            if (lc<=rc && a+b>=L && a+b<=R) res = (res+(rc-lc+1)*4)%mod;


            //L<=a+c<=R
            tmpl = max(L-a, lc), tmpr = min(R-a, rc);
            if(tmpl<=tmpr) res = (res+(tmpr-tmpl+1)*4)%mod;


            //L<=b+c<=R
            tmpl = max(L-b, lc); tmpr = min(R-b, rc);
            if(tmpl<=tmpr) res = (res+(tmpr-tmpl+1)*4)%mod;


            //L<=a+d<=R
            // --> ld <= n/c <= rd
            lo = 1; hi = n+2; ans = -1;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(n/mid>=L-a) {
                    ans = mid;
                    lo = mid+1;
                } else {
                    hi = mid-1;
                }
            }
            tmpr = ans;

            lo = 1; hi = n+2; ans = inf;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(n/mid<=R-a) {
                    hi = mid-1;
                    ans = mid;
                } else {
                    lo = mid+1;
                }
            }
            tmpl = ans;
            tmpl = max(tmpl, lc); tmpr = min(tmpr, rc);
            if(tmpl<=tmpr) res = (res+(tmpr-tmpl+1)*4)%mod;


            //L<=b+d<=R
            //--> ld <= n/c <= rd
            lo = 1; hi = n+2; ans = -1;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(n/mid>=L-b) {
                    ans = mid;
                    lo = mid+1;
                } else {
                    hi = mid-1;
                }
            }
            tmpr = ans;

            lo = 1; hi = n+2; ans = inf;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(n/mid<=R-b) {
                    ans = mid;
                    hi = mid-1;
                } else {
                    lo = mid+1;
                }
            }
            tmpl = ans;
            tmpl = max(tmpl, lc); tmpr = min(tmpr, rc);
            if(tmpl<=tmpr) res = (res+(tmpr-tmpl+1)*4)%mod;
            

            //L<=c+d<=R    
            lo=1; hi=rc+1; ans = -1;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(mid+n/mid>=L) {
                    ans = mid;
                    lo = mid+1;
                } else {
                    hi = mid-1;
                }
            }
            tmpr = ans;
            lo=1; hi=rc+1; ans = inf;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(mid+n/mid<=R) {
                    ans = mid;
                    hi = mid-1;
                } else {
                    lo = mid+1;
                }
            }
            tmpl = ans;
            tmpl = max(tmpl, lc); tmpr = min(tmpr, rc);
            if(tmpl<=tmpr) res = (res+(tmpr-tmpl+1)*4)%mod;
        }
    }
    cout << res;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

24 4 6

output:

12

result:

ok single line: '12'

Test #2:

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

input:

30 5 6

output:

4

result:

ok single line: '4'

Test #3:

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

input:

30 9 20

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 4026ms
memory: 3652kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

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

input:

51256 4 35

output:

29116

result:

ok single line: '29116'

Test #6:

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

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

input:

20603 5 167

output:

36556

result:

ok single line: '36556'

Test #9:

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

input:

37521 1 76

output:

46956

result:

ok single line: '46956'

Test #10:

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

input:

1 1 10

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 3965ms
memory: 3520kb

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

score: 0
Accepted
time: 3608ms
memory: 3588kb

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

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

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

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

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

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

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

score: 0
Accepted
time: 3888ms
memory: 3584kb

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

score: 0
Accepted
time: 3740ms
memory: 3616kb

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

score: 0
Accepted
time: 3913ms
memory: 3584kb

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0
Accepted
time: 3782ms
memory: 3588kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

score: 0
Accepted
time: 4018ms
memory: 3584kb

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

score: 0
Accepted
time: 4102ms
memory: 3660kb

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

score: 0
Accepted
time: 4129ms
memory: 3584kb

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

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

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

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

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

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

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

score: 0
Accepted
time: 4302ms
memory: 3624kb

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

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

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

score: 0
Accepted
time: 3898ms
memory: 3624kb

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

score: 0
Accepted
time: 4007ms
memory: 3488kb

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0
Accepted
time: 4164ms
memory: 3584kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

score: 0
Accepted
time: 4128ms
memory: 3584kb

input:

100000000000000 1 2

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 3953ms
memory: 3492kb

input:

100000000000000 10000000000000 100000000000000

output:

36

result:

ok single line: '36'
English 繁體中文 简体中文

服务器时间: 2024-12-02 17:06:09 | 开源项目