QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360686#959. Multiple?tvladmTL 26ms3672kbC++172.2kb2024-03-22 00:37:492024-03-22 00:37:50

Judging History

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

  • [2024-03-22 00:37:50]
  • 评测
  • 测评结果:TL
  • 用时:26ms
  • 内存:3672kb
  • [2024-03-22 00:37:49]
  • 提交

answer


#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int Mod = 998244353;

int phi(int n) {
    ll sol = n;
    int d = 2;
    while (d * d <= n) {
        int e = 0;
        while (n % d == 0) {
            n /= d;
            e++;
        }
        if (e > 0) {
            sol *= d - 1;
            sol /= d;
        }
        d++;
    }
    if (n > 1) {
        sol *= n - 1;
        sol /= n;
    }
    return sol;
}

int mul(int a, int b) {
    return 1LL * a * b % Mod;
}

int powm(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int dv(int a, int b) {
    return mul(a, powm(b, Mod - 2));
}

int comb(int n, int k) {
    int res = 1;
    for (int i = n - k + 1; i <= n; i++) {
        res = mul(res, i);
    }
    for (int i = 2; i <= k; i++) {
        res = dv(res, i);
    }
    return res;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    int n, k;
    cin >> n >> k;
    cout << mul(phi(n), comb(n - 1, k - 1));
    return 0;
}

详细

Test #1:

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

input:

4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

9 2

output:

48

result:

ok 1 number(s): "48"

Test #3:

score: 0
Accepted
time: 26ms
memory: 3672kb

input:

222222222 222222

output:

851798824

result:

ok 1 number(s): "851798824"

Test #4:

score: -100
Time Limit Exceeded

input:

998244352 249561088

output:


result: