QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353071 | #965. Trade | HKOI0# | WA | 1ms | 3512kb | C++20 | 2.2kb | 2024-03-13 20:37:31 | 2024-03-13 20:37:31 |
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 (__int128_t) pm((__int128_t) a * a % m, b / 2, m) * (b % 2 ? a : 1) % 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;
}
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();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3512kb
input:
2 5 1 1 10 11
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'