QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#580740	#5477. Cake Decoration	mrkiencf	AC ✓	2367ms	3760kb	C++14	4.2kb	2024-09-21 23:29:35	2024-09-21 23:29:40

Judging History

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

[2024-09-21 23:29:40]
评测

测评结果：AC
用时：2367ms
内存：3760kb

查看

[2024-09-21 23:29:35]
提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 1e6 + 50;
const int mod = 998244353;

int X, L, R, dem;

void Add(int &x, int y){
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}

int sqr4(int x){
    return x * x * x * x;
}

int sqr3(int x){
    return x * x * x;
}

bool check(int x){
    return L <= x && x <= R;
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    X = L = R = 1e14;
    cin >> X >> L >> R; R -= 1;

    int cnt = 0;
    /*for (int i = 1; i <= X; ++ i){
        for (int j = i + 1; j <= X; ++ j){
            for (int z = j + 1; z <= X; ++ z){
                for (int l = z + 1; l <= X; ++ l){
                    int x = i * z * j;
                    if (x * l <= X && x * (l + 1) > X){
                        cnt += check(i + j);
                        cnt += check(i + l);
                        cnt += check(i + z);
                        cnt += check(j + l);
                        cnt += check(j + z);
                        cnt += check(z + l);

                        //if (check(i + j)) cout << i << " " << j
                    }
                }
            }
        }
    }*/

    //cout << cnt * 4 << " ";

    for (int i = 1; sqr4(i) <= X; ++ i){
        int Y = X / i;
        for (int j = i + 1; sqr3(j) <= Y; ++ j){
            int Z = Y / j;

            int minZ = j + 1;
            int maxZ = sqrt(Z);
            maxZ -= ((Z / maxZ) == maxZ);

            if (minZ > maxZ) break;

            int minL = Z / maxZ;
            int maxL = Z / minZ;

            if (minL > maxL) continue;

            /// i j
            Add(dem, (maxZ - minZ + 1) * check(i + j) % mod);

            /// i z
            if (i <= R) Add(dem, max(0ll, min(maxZ, R - i) - max(L - i, minZ) + 1));

            /// j z
            if (j <= R) Add(dem, max(0ll, min(maxZ, R - j) - max(L - j, minZ) + 1));

            /// i l
            if (i <= R){
                int l = minZ, r = maxZ;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (Z / mid > R - i) l = mid + 1;
                    else r = mid - 1;
                }
                // l
                int rig = max(minZ, l);

                l = minZ; r = maxZ;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (Z / mid >= L - i) l = mid + 1;
                    else r = mid - 1;
                }
                // r
                r = min(maxZ, r);

                Add(dem, max(0ll, r - rig + 1));
                //cout << "i l " << max(0ll, r - rig + 1) << endl;
            }

            /// j l
            if (j <= R){
                int l = minZ, r = maxZ;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (Z / mid > R - j) l = mid + 1;
                    else r = mid - 1;
                }
                // l
                int rig = max(minZ, l);
                //cout << rig << " ";

                l = minZ; r = maxZ;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (Z / mid >= L - j) l = mid + 1;
                    else r = mid - 1;
                }
                // r
                r = min(maxZ, r);

                Add(dem, max(0ll, r - rig + 1));
                //cout << "j l " << max(0ll, r - rig + 1) << endl;
            }

            /// z l
            {
                int l = minZ, r = maxZ;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (Z / mid + mid > R) l = mid + 1;
                    else r = mid - 1;
                }
                // l
                int rig = max(minZ, l);

                l = minZ; r = maxZ;
                while (l <= r){
                    int mid = (l + r) / 2;
                    if (Z / mid + mid < L) r = mid - 1;
                    else l = mid + 1;
                }
                // r
                r = min(maxZ, r);

                Add(dem, max(0ll, r - rig + 1));
            }


        }
    }

    cout << (dem * 4) % mod;
}
/***
***/

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3600kb

input:

24 4 6

output:

result:

ok single line: '12'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

30 5 6

output:

result:

ok single line: '4'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

30 9 20

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 2214ms

memory: 3632kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3660kb

input:

51256 4 35

output:

result:

ok single line: '29116'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3572kb

input:

5845 10 163

output:

result:

ok single line: '10724'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3568kb

input:

47139 6 167

output:

result:

ok single line: '71716'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

20603 5 167

output:

result:

ok single line: '36556'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3712kb

input:

37521 1 76

output:

result:

ok single line: '46956'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

1 1 10

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 2177ms

memory: 3656kb

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

score: 0

Accepted

time: 1983ms

memory: 3612kb

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

score: 0

Accepted

time: 2011ms

memory: 3652kb

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

score: 0

Accepted

time: 2035ms

memory: 3636kb

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

score: 0

Accepted

time: 2123ms

memory: 3628kb

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

score: 0

Accepted

time: 2119ms

memory: 3564kb

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

score: 0

Accepted

time: 2031ms

memory: 3636kb

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

score: 0

Accepted

time: 2131ms

memory: 3636kb

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0

Accepted

time: 2056ms

memory: 3596kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

score: 0

Accepted

time: 2183ms

memory: 3564kb

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

score: 0

Accepted

time: 2301ms

memory: 3632kb

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

score: 0

Accepted

time: 2259ms

memory: 3628kb

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

score: 0

Accepted

time: 2159ms

memory: 3564kb

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

score: 0

Accepted

time: 2283ms

memory: 3756kb

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

score: 0

Accepted

time: 2132ms

memory: 3568kb

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

score: 0

Accepted

time: 2106ms

memory: 3636kb

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

score: 0

Accepted

time: 2122ms

memory: 3576kb

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

score: 0

Accepted

time: 1629ms

memory: 3760kb

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

score: 0

Accepted

time: 2292ms

memory: 3560kb

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0

Accepted

time: 2367ms

memory: 3688kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

score: 0

Accepted

time: 912ms

memory: 3688kb

input:

100000000000000 1 2

output:

result:

ok single line: '0'

Test #32:

score: 0

Accepted

time: 2129ms

memory: 3632kb

input:

100000000000000 10000000000000 100000000000000

output:

result:

ok single line: '36'