QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232077 | #959. Multiple? | JWRuixi | AC ✓ | 2058ms | 3556kb | C++20 | 2.0kb | 2023-10-29 20:33:20 | 2023-10-29 20:33:21 |
Judging History
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!
Details
Tip: Click on the bar to expand more detailed information
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"