2019年ICPC银川 Function！推柿子

传送门：https://nanti.jisuanke.com/t/42386

题意

$设f_a(x)=a^x，求解$

$$\sum_{a=2}^n\left ( a\sum_{b=a}^n\left \lfloor f_a^{-1}(b) \right \rfloor\left \lceil f_b^{-1}(a)\right \rceil \right ) mod\;998244353$$

思路

$根据f_a^{-1}(x)=\log_a^x可知，原式等于$

$$\sum_{a=2}^n\left ( a\sum_{b=a}^n\left \lfloor \log_a^{b}\right \rfloor\left \lceil \log_b^a\right \rceil \right ) $$

$因为b\ge a，所以\left \lceil \log_b^a\right \rceil=1，即$

$$\sum_{a=2}^n\left ( a\sum_{b=a}^n\left \lfloor \log_a^{b}\right \rfloor \right ) $$

$接下来考虑\log_a^b的贡献，我们知道\log_a^a=1,\log_a^{a^2}=2,\log_a^{a^k}=k.$

$而这些有多少个呢？1有a^2-a个，2有a^3-a^2个…$

$所以对于a^2<n的，遍历次幂计算贡献。$

$对于a^2>n，只有1这个贡献，所以我们只要遍历\sqrt n即可，n=1e12，very \;good!$

$不过对于a*a=n，有a^2-a个1，和1个2，另外计算即可。$

$对于a*a>n，贡献为a*(n-a+1)+(a+ 1)*(n-a)+…+n*1=\sum_{a=\sqrt n+1}^na*(n-a+1)$

$这一部分为：$

$$\frac{1}{2}(n+1)(\sqrt n+1+n)(n-\sqrt n)+\frac{1}{6}(n(n+1)(2n+1)-(\sqrt n-1)(\sqrt n)(2\sqrt n-1))$$

$最后整合计算即可。$

$复杂度为O(\sqrt n)。$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;
const ll mod = 998244353;

ll quick\_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

void solve() {
    ll n; cin >> n;
    ll ans = 0;
    ll a = 2;
    for( ;a * a <= n; a++) {
        if(a * a == n) {
            ans = (ans + a * ((n - a + 2) % mod) % mod) % mod; // a * a == n
        }
        else {
            ll t = a;
            ll k = 1;
            while(t * a <= n) {
                ans = (ans + t * (a - 1) % mod * a % mod * k  % mod) % mod;
                t = t * a;
                k++;
            }
            ans = (ans + (n - t + 1) % mod * a % mod * k % mod) % mod;
        }
    }
    ll inv2 = quick\_pow(2, mod - 2);
    ll inv6 = quick\_pow(6, mod - 2);
    // 后面的a都是只有1的贡献
    ans = (ans + ((n + 1) % mod) * ((n - a + 1) % mod) % mod * ((a + n) % mod) % mod * inv2 % mod) % mod;
    ans = (ans - (n % mod) * ((n + 1) % mod) % mod * ((2ll * n + 1) % mod) % mod * inv6 % mod + (a - 1) * a % mod * (2ll * a - 1) % mod * inv6 % mod) % mod;
    cout << (ans % mod + mod) % mod << endl;
}

signed main() {
    solve();
}