QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232077#959. Multiple?JWRuixiAC ✓2058ms3556kbC++202.0kb2023-10-29 20:33:202023-10-29 20:33:21

Judging History

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

  • [2023-10-29 20:33:21]
  • 评测
  • 测评结果:AC
  • 用时:2058ms
  • 内存:3556kb
  • [2023-10-29 20:33:20]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx,avx,avx2")
// #define ATC
#define LL long long
#define eb emplace_back
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FIO(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
using namespace std;

#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template<typename _Tp>
    inline void write(_Tp x) {
        static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);
    }
}

using IO::read;
using IO::write;

constexpr int mod = 998244353;
int n, k;

inline int ksm(int b, int k) {
    int r = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod) if (k & 1) r = (LL)r * b % mod;
    return r;
}

inline int Binom (int n, int m) {
    int r = 1;
    for (int i = 1; i <= m; i++) r = (LL)r * i % mod;
    r = ksm(r, mod - 2);
    for (int i = 0; i < m; i++) r = (LL)r * (n - i) % mod;
    return r;
}

int main() {
    n = read(), k = read();
    int r = Binom(n - 1, k - 1);
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            r = (LL)r * (i - 1) % mod;
            n /= i;
            while (n % i == 0) r = (LL)r * i % mod, n /= i;
        }
    }
    if (n > 1) {
        r = (LL)r * (n - 1) % mod;
    }
    write(r);
}
// I love WHQ!

详细

Test #1:

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

input:

4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

9 2

output:

48

result:

ok 1 number(s): "48"

Test #3:

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

input:

222222222 222222

output:

851798824

result:

ok 1 number(s): "851798824"

Test #4:

score: 0
Accepted
time: 2058ms
memory: 3348kb

input:

998244352 249561088

output:

100663296

result:

ok 1 number(s): "100663296"

Test #5:

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

input:

62 3

output:

54900

result:

ok 1 number(s): "54900"

Test #6:

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

input:

328 42

output:

9805666

result:

ok 1 number(s): "9805666"

Test #7:

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

input:

318 67

output:

603200201

result:

ok 1 number(s): "603200201"

Test #8:

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

input:

1368 16

output:

105422469

result:

ok 1 number(s): "105422469"

Test #9:

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

input:

50715 7550

output:

618459631

result:

ok 1 number(s): "618459631"

Test #10:

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

input:

76973 14799

output:

468374999

result:

ok 1 number(s): "468374999"

Test #11:

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

input:

99380 19487

output:

687640903

result:

ok 1 number(s): "687640903"

Test #12:

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

input:

21790 2731

output:

101785330

result:

ok 1 number(s): "101785330"

Test #13:

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

input:

690640 123082

output:

867724310

result:

ok 1 number(s): "867724310"

Test #14:

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

input:

491216 62882

output:

359870082

result:

ok 1 number(s): "359870082"

Test #15:

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

input:

331430 27658

output:

336996189

result:

ok 1 number(s): "336996189"

Test #16:

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

input:

171644 19051

output:

291982732

result:

ok 1 number(s): "291982732"

Test #17:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

4480506 212264

output:

613147340

result:

ok 1 number(s): "613147340"

Test #18:

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

input:

436959 48003

output:

451377650

result:

ok 1 number(s): "451377650"

Test #19:

score: 0
Accepted
time: 11ms
memory: 3356kb

input:

6393409 1221473

output:

573934740

result:

ok 1 number(s): "573934740"

Test #20:

score: 0
Accepted
time: 6ms
memory: 3320kb

input:

7381276 607288

output:

895895324

result:

ok 1 number(s): "895895324"

Test #21:

score: 0
Accepted
time: 10ms
memory: 3556kb

input:

7951897 1124478

output:

9197219

result:

ok 1 number(s): "9197219"

Test #22:

score: 0
Accepted
time: 15ms
memory: 3348kb

input:

10822617 1773938

output:

200848469

result:

ok 1 number(s): "200848469"

Test #23:

score: 0
Accepted
time: 14ms
memory: 3264kb

input:

13693337 1629029

output:

390448867

result:

ok 1 number(s): "390448867"

Test #24:

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

input:

21596632 5162607

output:

286800922

result:

ok 1 number(s): "286800922"

Test #25:

score: 0
Accepted
time: 564ms
memory: 3328kb

input:

483262472 68378363

output:

805389870

result:

ok 1 number(s): "805389870"

Test #26:

score: 0
Accepted
time: 631ms
memory: 3548kb

input:

504666092 76509085

output:

487083023

result:

ok 1 number(s): "487083023"

Test #27:

score: 0
Accepted
time: 686ms
memory: 3548kb

input:

828059612 83073089

output:

328505426

result:

ok 1 number(s): "328505426"

Test #28:

score: 0
Accepted
time: 81ms
memory: 3264kb

input:

153208783 10166904

output:

109080048

result:

ok 1 number(s): "109080048"

Test #29:

score: 0
Accepted
time: 560ms
memory: 3264kb

input:

476602303 67863017

output:

414678607

result:

ok 1 number(s): "414678607"

Test #30:

score: 0
Accepted
time: 347ms
memory: 3396kb

input:

498005923 42023403

output:

754443127

result:

ok 1 number(s): "754443127"

Test #31:

score: 0
Accepted
time: 197ms
memory: 3396kb

input:

125144994 23866191

output:

754831055

result:

ok 1 number(s): "754831055"

Test #32:

score: 0
Accepted
time: 36ms
memory: 3548kb

input:

146548614 4304228

output:

655902521

result:

ok 1 number(s): "655902521"