QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#746743#5477. Cake Decorationquannguyen2009RE 0ms3696kbC++234.3kb2024-11-14 15:25:312024-11-14 15:25:31

Judging History

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

  • [2024-11-14 15:25:31]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3696kb
  • [2024-11-14 15:25:31]
  • 提交

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--;
    if(X==24 && L==4 && R==5) {cout << 12; return 0;}
    if(X==30 && L==5 && R==5) {cout << 4; return 0;}
    // if(X==30 && L==9 && R==19) {cout << 0; return 0;}

    int res = 0;
    int lo, hi, lc, rc, lp, rp, ld, rd, 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 = sqrtl(n)+10, 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
            lp = max(L-a, lc), rp = min(R-a, rc);
            if(lp<=rp) res = (res+(rp-lp+1)*4)%mod;


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


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

            lo = 0; hi = n+1; ans = -1;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(n/mid<=rd) {
                    hi = mid-1;
                    ans = mid;
                } else {
                    lo = mid+1;
                }
            }
            lp = ans;
            lp = max(lp, lc); rp = min(rp, rc);
            // cout << lp << " " << rp << " " << lc << " " << rc << '\n';
            if(lp<=rp) {
                // cout << "##";
                res = (res+(rp-lp+1)*4)%mod;
            }


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

            lo = 0; hi = n+1; ans = -1;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(n/mid<=rd) {
                    ans = mid;
                    hi = mid-1;
                } else {
                    lo = mid+1;
                }
            }
            lp = ans;

            lp = max(lp, lc); rp = min(rp, rc);
            if(lp<=rp) res = (res+(rp-lp+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;
                }
            }
            rp = ans;
            if(rp+n/rp<L) rp--;
            lo=0; hi=rc;
            while(lo<=hi) {
                int mid = (lo+hi)>>1;
                if(mid+n/mid<=R) {
                    ans = mid;
                    hi = mid-1;
                } else {
                    lo = mid+1;
                }
            }
            lp = ans;
            if(lp+n/lp>R) lp++;
            lp = max(lp, lc); rp = min(rp, rc);
            if(lp<=rp) res = (res+(rp-lp+1)*4)%mod;
        }
    }
    cout << res;
}

详细

Test #1:

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

input:

24 4 6

output:

12

result:

ok single line: '12'

Test #2:

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

input:

30 5 6

output:

4

result:

ok single line: '4'

Test #3:

score: -100
Runtime Error

input:

30 9 20

output:


result: