QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429678#8761. 另一个计数问题SunsetGlow95AC ✓1117ms17372kbC++142.1kb2024-06-02 19:13:172024-06-02 19:13:19

Judging History

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

  • [2024-06-02 19:13:19]
  • 评测
  • 测评结果：AC
  • 用时：1117ms
  • 内存：17372kb
查看
  • [2024-06-02 19:13:17]
  • 提交

answer

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

using ll = long long;
const int MXSQ = 3.2e5;
const int DVS = 998244353;
const int INV2 = 499122177;
const int INV6 = 166374059;
int pms[MXSQ], pid;
bool notp[MXSQ];
ll N;

pair<int, int> cal(ll n) {
  static ll ptn[MXSQ * 2];
  static int bn[MXSQ];
  static int sn[MXSQ];
  static int sm[MXSQ * 2], sm2[MXSQ * 2];
  int pts(0);
  for (ll i(1), r(0); i <= n; ++pts, i = r + 1) {
    ll v(n / i);
    r = n / (n / i);
    ptn[pts] = v;
    if (v <= n / v) sn[v] = pts;
    else bn[n / v] = pts;
    sm[pts] = (v % DVS * ((v + 1) % DVS) % DVS * INV2 % DVS) % DVS;
    sm2[pts] = (v % DVS * ((v + 1) % DVS) % DVS * ((2 * v + 1) % DVS) % DVS * INV6 % DVS) % DVS;
  }
  for (int i(0); i != pid; ++i) {
    if (pms[i] * 1LL * pms[i] > n) break;
    for (int j(0); pms[i] * 1LL * pms[i] <= ptn[j]; ++j) {
      ll subv(ptn[j] / pms[i]);
      int subid(subv <= n / subv ? sn[subv] : bn[n / subv]);
      sm[j] = (sm[j] - pms[i] * 1LL * (sm[subid] - sm[sn[pms[i] - 1]] + DVS) % DVS + DVS) % DVS;
      sm2[j] = (sm2[j] - pms[i] * 1LL * pms[i] % DVS * (sm2[subid] - sm2[sn[pms[i] - 1]] + DVS) % DVS + DVS) % DVS;
    }
  }
  return make_pair((sm[0] - 1 + DVS) % DVS, (sm2[0] - 1 + DVS) % DVS);
}

int main() {
  notp[0] = notp[1] = true;
  for (int i(2); i != MXSQ; ++i) {
    if (!notp[i]) pms[pid++] = i;
    for (int j(0); j != pid && i * pms[j] < MXSQ; ++j) {
      notp[i * pms[j]] = true;
      if (i % pms[j] == 0) break;
    }
  }
  cin >> N;
  pair<int, int> lp(cal(N / 2)), rp(cal(N));
//cout << lp.first << ' ' << lp.second << endl;
//cout << rp.first << ' ' << rp.second << endl;
  int ps((rp.first - lp.first + DVS) % DVS);
  int p2s((rp.second - lp.second + DVS) % DVS);
  N %= DVS;
  int s((N * 1LL * (N + 1) % DVS * INV2 % DVS - 1 + DVS) % DVS);
  int s2((N * 1LL * (N + 1) % DVS * (2 * N + 1) % DVS * INV6 % DVS - 1 + DVS) % DVS);
//cout << s << ' ' << s2 << ' ' << ps << ' ' << p2s << endl;
  cout << (((s * 1LL * s % DVS + ps * 1LL * ps % DVS) % DVS + p2s) % DVS - (s2 + 2LL * s * ps) % DVS + DVS) * INV2 % DVS << endl;
  return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

5

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 0
Accepted
time: 3ms
memory: 10280kb

input:

6

output:

80

result:

ok 1 number(s): "80"

Test #4:

score: 0
Accepted
time: 3ms
memory: 10224kb

input:

7

output:

80

result:

ok 1 number(s): "80"

Test #5:

score: 0
Accepted
time: 3ms
memory: 12144kb

input:

8

output:

200

result:

ok 1 number(s): "200"

Test #6:

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

input:

9

output:

407

result:

ok 1 number(s): "407"

Test #7:

score: 0
Accepted
time: 3ms
memory: 12264kb

input:

10

output:

937

result:

ok 1 number(s): "937"

Test #8:

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

input:

79

output:

3224298

result:

ok 1 number(s): "3224298"

Test #9:

score: 0
Accepted
time: 3ms
memory: 10220kb

input:

123

output:

21077222

result:

ok 1 number(s): "21077222"

Test #10:

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

input:

158

output:

57411585

result:

ok 1 number(s): "57411585"

Test #11:

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

input:

285

output:

605750829

result:

ok 1 number(s): "605750829"

Test #12:

score: 0
Accepted
time: 3ms
memory: 10280kb

input:

355

output:

509863120

result:

ok 1 number(s): "509863120"

Test #13:

score: 0
Accepted
time: 3ms
memory: 14376kb

input:

484

output:

311440260

result:

ok 1 number(s): "311440260"

Test #14:

score: 0
Accepted
time: 3ms
memory: 12188kb

input:

520

output:

102191845

result:

ok 1 number(s): "102191845"

Test #15:

score: 0
Accepted
time: 3ms
memory: 10096kb

input:

706

output:

300787918

result:

ok 1 number(s): "300787918"

Test #16:

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

input:

747

output:

505062591

result:

ok 1 number(s): "505062591"

Test #17:

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

input:

784

output:

181810798

result:

ok 1 number(s): "181810798"

Test #18:

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

input:

76879

output:

716166793

result:

ok 1 number(s): "716166793"

Test #19:

score: 0
Accepted
time: 3ms
memory: 10224kb

input:

209295

output:

753032272

result:

ok 1 number(s): "753032272"

Test #20:

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

input:

220895

output:

874612082

result:

ok 1 number(s): "874612082"

Test #21:

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

input:

243390

output:

68635874

result:

ok 1 number(s): "68635874"

Test #22:

score: 0
Accepted
time: 3ms
memory: 10244kb

input:

414767

output:

862578797

result:

ok 1 number(s): "862578797"

Test #23:

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

input:

431662

output:

231728766

result:

ok 1 number(s): "231728766"

Test #24:

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

input:

521130

output:

106207351

result:

ok 1 number(s): "106207351"

Test #25:

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

input:

668419

output:

580625063

result:

ok 1 number(s): "580625063"

Test #26:

score: 0
Accepted
time: 3ms
memory: 12204kb

input:

700378

output:

790849562

result:

ok 1 number(s): "790849562"

Test #27:

score: 0
Accepted
time: 3ms
memory: 10292kb

input:

965876

output:

856082142

result:

ok 1 number(s): "856082142"

Test #28:

score: 0
Accepted
time: 44ms
memory: 10468kb

input:

998244350

output:

539142456

result:

ok 1 number(s): "539142456"

Test #29:

score: 0
Accepted
time: 41ms
memory: 14380kb

input:

998244351

output:

730264865

result:

ok 1 number(s): "730264865"

Test #30:

score: 0
Accepted
time: 45ms
memory: 12580kb

input:

998244352

output:

326703895

result:

ok 1 number(s): "326703895"

Test #31:

score: 0
Accepted
time: 41ms
memory: 14312kb

input:

998244353

output:

326703895

result:

ok 1 number(s): "326703895"

Test #32:

score: 0
Accepted
time: 41ms
memory: 12536kb

input:

998244354

output:

730264864

result:

ok 1 number(s): "730264864"

Test #33:

score: 0
Accepted
time: 40ms
memory: 12508kb

input:

998244355

output:

539142451

result:

ok 1 number(s): "539142451"

Test #34:

score: 0
Accepted
time: 41ms
memory: 14188kb

input:

998244356

output:

751581014

result:

ok 1 number(s): "751581014"

Test #35:

score: 0
Accepted
time: 70ms
memory: 12572kb

input:

2165916141

output:

216013547

result:

ok 1 number(s): "216013547"

Test #36:

score: 0
Accepted
time: 104ms
memory: 12568kb

input:

3550627266

output:

318019384

result:

ok 1 number(s): "318019384"

Test #37:

score: 0
Accepted
time: 238ms
memory: 14380kb

input:

11640239920

output:

137498099

result:

ok 1 number(s): "137498099"

Test #38:

score: 0
Accepted
time: 303ms
memory: 14312kb

input:

16191777349

output:

991399721

result:

ok 1 number(s): "991399721"

Test #39:

score: 0
Accepted
time: 479ms
memory: 16284kb

input:

31326230483

output:

99981147

result:

ok 1 number(s): "99981147"

Test #40:

score: 0
Accepted
time: 493ms
memory: 15044kb

input:

32810385543

output:

284259680

result:

ok 1 number(s): "284259680"

Test #41:

score: 0
Accepted
time: 542ms
memory: 16284kb

input:

37368395332

output:

511468046

result:

ok 1 number(s): "511468046"

Test #42:

score: 0
Accepted
time: 574ms
memory: 16360kb

input:

40002331093

output:

282851705

result:

ok 1 number(s): "282851705"

Test #43:

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

input:

82884464396

output:

767050832

result:

ok 1 number(s): "767050832"

Test #44:

score: 0
Accepted
time: 1065ms
memory: 17068kb

input:

96506992785

output:

31413975

result:

ok 1 number(s): "31413975"

Test #45:

score: 0
Accepted
time: 1099ms
memory: 16444kb

input:

99999999995

output:

456189842

result:

ok 1 number(s): "456189842"

Test #46:

score: 0
Accepted
time: 1117ms
memory: 16580kb

input:

99999999996

output:

516138273

result:

ok 1 number(s): "516138273"

Test #47:

score: 0
Accepted
time: 1101ms
memory: 16972kb

input:

99999999997

output:

136420410

result:

ok 1 number(s): "136420410"

Test #48:

score: 0
Accepted
time: 1100ms
memory: 17372kb

input:

99999999998

output:

841974696

result:

ok 1 number(s): "841974696"

Test #49:

score: 0
Accepted
time: 1093ms
memory: 16932kb

input:

99999999999

output:

164762165

result:

ok 1 number(s): "164762165"

Test #50:

score: 0
Accepted
time: 1099ms
memory: 16788kb

input:

100000000000

output:

627965619

result:

ok 1 number(s): "627965619"
English 繁體中文 简体中文

Server Time: 2025-01-21 04:47:36 | OpenSource Project