QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353071#965. TradeHKOI0#WA 1ms3512kbC++202.2kb2024-03-13 20:37:312024-03-13 20:37:31

Judging History

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

  • [2024-03-13 20:37:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3512kb
  • [2024-03-13 20:37:31]
  • 提交

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'