2019徐州网络赛H题解

本来在赛场上推完了公式，不是实现难度有点高，20多分钟根本rush不完，我太难了。

对于和来说当的时候只需要做质数个数和以及质数和两个就可以解决问题了，当时我们直接暴力就行了

//author Forsaken
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<numeric>
#define lowbit(x) ((x) & (-(x)))
#define FRIN freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\1.in", "r", stdin)
#define FROUT freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\1.out", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%lld\n", x)
#define outu(x) printf("%u\n", x)
#define memset0(arr) memset(arr, 0, sizeof(arr))
#define il inline
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 1e5;
const int INF = 0x7fffffff;
const int mod = 998244353;
const double eps = 1e-7;
const double Pi = acos(-1.0);
il int read_int() {
    char c;
    int ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
il ll read_ll() {
    char c;
    ll ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
il ll quick_pow(ll base, ll index, ll p) {
    ll res = 1;
    while (index) {
        if (index & 1)res = res * base % p;
        base = base * base % p;
        index >>= 1;
    }
    return res;
}
//线性筛
bool is_prime[maxn + 5];
int prime[maxn + 5], cnt;
ll sp[maxn + 5];
void init(int n) {
    for (int i = 2; i <= n; ++i)is_prime[i] = true;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            ++cnt;
            prime[cnt] = sp[cnt] = i;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            is_prime[i * prime[j]] = false;
            if (i % prime[j] == 0)break;
        }
    }
    for (int i = 1; i <= cnt; ++i)sp[i] = (sp[i] + sp[i - 1]) % mod;
}
//min筛
int m, id1[maxn + 5], id2[maxn + 5];
ll g1[2 * maxn + 5], g2[2 * maxn + 5], v[2 * maxn + 5], block;
ll n, inv;
void min25() {
    block = sqrt(n);
    init(block);
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        v[++m] = n / l;
        g1[m] = v[m] % mod - 1, g2[m] = (v[m] + 1) % mod * (v[m] % mod) % mod * inv % mod - 1;
        if (v[m] <= block)id1[v[m]] = m;
        else id2[n / v[m]] = m;
    }
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 1; j <= m && 1ll * prime[i] * prime[i] <= v[j]; ++j) {
            int id = (v[j] / prime[i] <= block) ? id1[v[j] / prime[i]] : id2[n / (v[j] / prime[i])];
            g1[j] -= (g1[id] - i + 1) % mod;
            g1[j] %= mod;
            g2[j] -= (sp[i] - sp[i - 1]) * (g2[id] - sp[i - 1]) % mod;
            g2[j] %= mod;
        }
    }
}

ll solve(ll n) {
    ll res = 0;
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        int idr = ((r <= block) ? id1[r] : id2[n / r]), idl = (((l - 1) <= block) ? id1[l - 1] : id2[n / (l - 1)]);
        res += (n / l) % mod * ((n + 1) % mod) % mod * ((g1[idr] - g1[idl]) % mod) % mod;
        res -= (n / l) % mod * ((n / l + 1) % mod) % mod * inv % mod * ((g2[idr] - g2[idl]) % mod) % mod;
        res %= mod;
    }
    for (int i = 1; i <= cnt; ++i) {
        ll v = 1ll * prime[i] * prime[i];
        for (; v <= n; v = v * prime[i]) {
            res += (n + 1) % mod * ((n / v) % mod) % mod;
            res -= (n / v) % mod * ((n / v + 1) % mod) % mod * inv % mod * (v % mod) % mod;
            res %= mod;
        }
    }
    if (res < 0)res += mod;
    return res;
}
int main()
{
    inv = quick_pow(2, mod - 2, mod);
    n = read_ll();
    min25();
    ll res = solve(n);
    outld(res);
    return 0;
}