QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#93825	#5817. 小学生数学题	HaccerKat	100 ✓	761ms	158528kb	C++20	7.2kb	2023-04-03 00:35:03	2023-04-03 00:35:07

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-03 00:35:07]
评测

测评结果：100
用时：761ms
内存：158528kb

查看

[2023-04-03 00:35:03]
提交

answer

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

/*
000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
                        0000000
DO IT NOW!!!
*/

// using u128 = __uint128_t;
// using i128 = __int128;
constexpr int mod = 998244353;
const int mod2 = 998244352;
const int N = 20000005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
string s;
int n, m, k, qq;
int sieve[N], f[N];
int add(int x, int y) {
    return (x + y >= mod ? x + y - mod : x + y);
}

int mul(int x, int y) {
    return (ll)x * y % mod;    
}

int power(int x, int y) {
    int res = 1;
    while (y > 0) {
        if (y & 1) res = mul(res, x);
        x = mul(x, x);
        y >>= 1;
    }
    
    return res;
}

void solve() {
    cin >> n >> k;
    int out = 1, p = (ll)(mod - 2) * k % mod2, cur = 1;
    for (int i = 2; i <= n; i++) {
        // dbgm(n, i);
        cur = mul(cur, i);
        if (sieve[i] != 0) {
            f[i] = mul(f[sieve[i]], f[i / sieve[i]]);
            out = add(mul(f[i], cur), out);
            // dbgm(out, cur);
            continue;
        }
        
        else {
            f[i] = power(i, p);
            out = add(mul(f[i], cur), out);
        }
        
        if ((ll)i * i > n) continue;
        for (int j = i * i; j <= n; j += i) {
            sieve[j] = i;
        }
        
        // dbgm(out, cur);
    }
    
    // dbg(f);
    cout << out << "\n";
    
/*
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000                                     000000000000
000000000000000000000000000000000000000000000    000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000    000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000    000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000    000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000    000000000000000000000000000000000000000000000
*/

}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

源文件, 语言: C++20

详细

Test #1:

score: 10

Accepted

time: 323ms

memory: 77556kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 268ms

memory: 76936kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 287ms

memory: 75144kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 206ms

memory: 61344kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 251ms

memory: 67340kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 342ms

memory: 82840kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 633ms

memory: 143200kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 761ms

memory: 158528kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 688ms

memory: 153348kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 629ms

memory: 145380kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed