QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#353251 | #959. Multiple? | HKOI0 | TL | 69ms | 3840kb | C++20 | 2.3kb | 2024-03-13 23:47:30 | 2024-03-13 23:47:32 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
ll pm(ll a, ll b, ll m){
if (b == 0) return 1;
return pm( a * a % m, b / 2, m) * (b % 2 ? a : 1) % m;
}
ll mi(ll a, ll m){
return pm(a, m - 2, m);
}
bool is_comp(ll a, ll n){
ll s = n - 1, d = 0; while (s % 2 == 0) s /= 2, ++d;
ll x = pm(a, s, n);
if (x == 1) return false;
for (int i = 0; i < d; i++) {
if (x == n - 1) return false;
x = (__int128_t) x * x % n;
}
return true;
}
bool is_prime(ll n){
if (n <= 1) return false;
for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n == a) return true;
if (is_comp(a, n)) return false;
}
return true;
}
ll c = 20240313;
ll f(ll x, ll n){
return (__int128_t) x * x % n + c;
}
mt19937_64 rng(42);
vector<ll> pf;
void find_factor(ll n){
if (n == 1) return;
if (n == 4) {
pf.push_back(2);
pf.push_back(2);
return;
}
if (is_prime(n)) {
pf.push_back(n);
return;
}
while (true) {
ll a = rng() % (n - 1) + 1;
ll b = f(a, n);
while (gcd(a - b, n) == 1) {
a = f(a, n), b = f(f(b, n), n);
}
if (gcd(a - b, n) == n) {
--c; continue;
}
ll d = gcd(a - b, n);
find_factor(d);
find_factor(n / d);
break;
}
}
vector<ll> factorise(ll n){
pf.clear();
find_factor(n);
sort(pf.begin(), pf.end());
pf.resize(unique(pf.begin(), pf.end()) - pf.begin());
return pf;
}
ll totient(ll n){
map<int, int> mp;
for (auto p : factorise(n)) {
mp[p]++;
}
ll res = n;
for (auto [a, b] : mp) {
res = res / a * (a - 1);
}
return res;
}
const int MOD = 998244353;
void solve() {
int n, k; cin >> n >> k;
int ans = 1;
for (int i = n - 1; i >= n - k + 1; i--) {
ans *= i; ans %= MOD;
}
for (int i = 1; i <= k - 1; i++) {
ans *= mi(i, MOD); ans %= MOD;
}
ans *= totient(n); ans %= MOD;
cout << ans << endl;
}
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
4 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
9 2
output:
48
result:
ok 1 number(s): "48"
Test #3:
score: 0
Accepted
time: 69ms
memory: 3556kb
input:
222222222 222222
output:
851798824
result:
ok 1 number(s): "851798824"
Test #4:
score: -100
Time Limit Exceeded
input:
998244352 249561088