QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152202#5477. Cake Decorationnathanlee726AC ✓1113ms3812kbC++172.5kb2023-08-27 18:30:012023-08-27 18:30:02

Judging History

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

  • [2023-08-27 18:30:02]
  • 评测
  • 测评结果:AC
  • 用时:1113ms
  • 内存:3812kb
  • [2023-08-27 18:30:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using Int = long long;

template <class T> void pv(T a, T b) {
  for (T i = a; i != b; ++i) cerr << *i << " ";
  cerr << endl;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}

// maroon shakyou-modint
using ll=long long;
const uint mod=998244353;
struct mint{
  uint v;
  mint(ll vv=0){s(vv%mod+mod);}
  mint& s(uint vv){
    v=vv<mod?vv:vv-mod;
    return *this;
  }
  mint operator-()const{return mint()-*this;}
  mint&operator+=(mint r){return s(v+r.v);}
  mint&operator-=(mint r){return s(v+mod-r.v);}
  mint&operator*=(mint r){v=(unsigned ll)v*r.v%mod;return *this;}
  mint&operator/=(mint r){return *this*=r.inv();}
  mint operator+(mint r)const{return mint(*this)+=r;}
  mint operator-(mint r)const{return mint(*this)-=r;}
  mint operator*(mint r)const{return mint(*this)*=r;}
  mint operator/(mint r)const{return mint(*this)/=r;}
  mint pow(ll n)const{
    if(n<0)return inv().pow(-n);
    mint res(1),x(*this);
    while(n){
      if(n&1)res*=x;
      x*=x;
      n>>=1;
    }
    return res;
  }
  mint inv()const{return pow(mod-2);}
};

ostream &operator<<(ostream &os, mint a) {
  return os << a.v;
}


mint solve(const Int X, const Int R) {
  mint ans = 0;
  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) {
      const Int y = X / (a * b);
      Int lb = b + 1;
      Int ub = sqrt((long double)y);
      for (; ub * (ub + 1) > y; --ub) {}
      
      auto add = [&](Int c0, Int c1) -> void {
// if(X<=30)cerr<<a<<" "<<b<<": ["<<c0<<", "<<c1<<"]"<<endl;
        if (c0 <= c1) {
          ans += (c1 - c0 + 1);
        }
      };
      
      // a+b
      if (a + b < R) add(lb, ub);
      // a+c, b+c
      add(lb, min(ub, R - a - 1));
      add(lb, min(ub, R - b - 1));
      // a+d, b+d
      if (R - a > 0) add(max(lb, y / (R - a) + 1), ub);
      if (R - b > 0) add(max(lb, y / (R - b) + 1), ub);
      // c+d
      Int lo = lb - 1, hi = ub + 1;
      for (; lo + 1 < hi; ) {
        const Int mid = (lo + hi) / 2;
        ((mid + y / mid < R) ? hi : lo) = mid;
      }
      add(hi, ub);
    }
  }
  return ans;
}

int main() {
  Int X, L, R;
  for (; ~scanf("%lld%lld%lld", &X, &L, &R); ) {
    mint ans = 0;
    ans += solve(X, R);
    ans -= solve(X, L);
    ans *= 4;
    printf("%u\n", ans.v);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

24 4 6

output:

12

result:

ok single line: '12'

Test #2:

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

input:

30 5 6

output:

4

result:

ok single line: '4'

Test #3:

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

input:

30 9 20

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1070ms
memory: 3764kb

input:

100000000000000 1 100000000000000

output:

288287412

result:

ok single line: '288287412'

Test #5:

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

input:

51256 4 35

output:

29116

result:

ok single line: '29116'

Test #6:

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

input:

5845 10 163

output:

10724

result:

ok single line: '10724'

Test #7:

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

input:

47139 6 167

output:

71716

result:

ok single line: '71716'

Test #8:

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

input:

20603 5 167

output:

36556

result:

ok single line: '36556'

Test #9:

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

input:

37521 1 76

output:

46956

result:

ok single line: '46956'

Test #10:

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

input:

1 1 10

output:

0

result:

ok single line: '0'

Test #11:

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

input:

97083668416826 7 3808058212682

output:

392082021

result:

ok single line: '392082021'

Test #12:

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

input:

81206220725808 2 45630676823009

output:

956896057

result:

ok single line: '956896057'

Test #13:

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

input:

83357713762616 8 7064282922851

output:

238276229

result:

ok single line: '238276229'

Test #14:

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

input:

85445471832361 6 56105073865950

output:

611528255

result:

ok single line: '611528255'

Test #15:

score: 0
Accepted
time: 1029ms
memory: 3580kb

input:

92699451513867 7 40224031632009

output:

527678799

result:

ok single line: '527678799'

Test #16:

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

input:

91239680645595 2 6753821

output:

949101816

result:

ok single line: '949101816'

Test #17:

score: 0
Accepted
time: 983ms
memory: 3704kb

input:

84407166448013 9 9804427

output:

100140616

result:

ok single line: '100140616'

Test #18:

score: 0
Accepted
time: 1031ms
memory: 3704kb

input:

92300784798569 1 7627255

output:

506797132

result:

ok single line: '506797132'

Test #19:

score: 0
Accepted
time: 995ms
memory: 3804kb

input:

86360099055961 16 9430857

output:

909028853

result:

ok single line: '909028853'

Test #20:

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

input:

96378494166704 16 4791452

output:

961637838

result:

ok single line: '961637838'

Test #21:

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

input:

92800119725342 19 71735

output:

549693103

result:

ok single line: '549693103'

Test #22:

score: 0
Accepted
time: 1088ms
memory: 3796kb

input:

99241248175798 28 509556

output:

885647806

result:

ok single line: '885647806'

Test #23:

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

input:

90117794770692 17 324480

output:

701148580

result:

ok single line: '701148580'

Test #24:

score: 0
Accepted
time: 1094ms
memory: 3580kb

input:

99417213318477 67 305057

output:

478902343

result:

ok single line: '478902343'

Test #25:

score: 0
Accepted
time: 1027ms
memory: 3808kb

input:

90584131165693 78 897660

output:

879735139

result:

ok single line: '879735139'

Test #26:

score: 0
Accepted
time: 1033ms
memory: 3812kb

input:

92129120236843 702 5645

output:

28323443

result:

ok single line: '28323443'

Test #27:

score: 0
Accepted
time: 1025ms
memory: 3764kb

input:

90203225783100 802 6272

output:

966952096

result:

ok single line: '966952096'

Test #28:

score: 0
Accepted
time: 967ms
memory: 3580kb

input:

82248112022135 533 2266

output:

280479804

result:

ok single line: '280479804'

Test #29:

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

input:

84853900427215 368 25431

output:

471070321

result:

ok single line: '471070321'

Test #30:

score: 0
Accepted
time: 1113ms
memory: 3804kb

input:

91754392379969 149 24312

output:

577285220

result:

ok single line: '577285220'

Test #31:

score: 0
Accepted
time: 1060ms
memory: 3640kb

input:

100000000000000 1 2

output:

0

result:

ok single line: '0'

Test #32:

score: 0
Accepted
time: 1081ms
memory: 3612kb

input:

100000000000000 10000000000000 100000000000000

output:

36

result:

ok single line: '36'