ICPC 2019 银川 F - Function! 题解

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

题目链接

题意

对于给定函数：

f_{a} (x) = a^{x} (a > 0 \land a \neq 1)

$n \ (n \le 10^{12})$ 求如下式子的值

\sum_{a = 2}^{n} (a \times \sum_{b = a}^{n} ⌊ f_{a}^{- 1} (b) ⌋ \times ⌈ f_{b}^{- 1} (a) ⌉)

前置知识

反函数（逆函数）

$f(x)$ $f^{-1}(x)$ $f(x)$ $f(x)$ $f^{-1}(x)$ 了。

$f(x)$ 显然指数函数的反函数即对数函数，可以这样理解：

$f_a(x) = a^x$ $x$ $a^x$ $f^{-1}_a(a^x) = x$ $\xi = a^x$ $f_a^{-1}(\xi) = \log_a^\xi$ 。

逆元

TODO

对于求逆元的方法，以及除数较小时如何不用逆元，这里不再赘述，以后有时间可能开个逆元的坑。

分析

简单的转换

由前置知识可以得出题目中的式子等价于如下式子：

\sum_{a = 2}^{n} (a \times \sum_{b = a}^{n} ⌊ \log_{a}^{b} ⌋ \times ⌈ \log_{b}^{a} ⌉)

Tips

$TLE$ $100KB$ $1 \times 10^4$ 左右。

$O(n^2)$ 做法

$a, b$ $10^4$ 以内的数据。

$O(n)$ 做法

考虑题中式子的性质：

$b \ge a$ 。

则显然有

\log_{b}^{a} \in (0, 1]

即

⌈ \log_{b}^{a} ⌉ = 1

$\log_a^b$ ，可以发现如下性质：

\log_{a}^{b} \in [1, 2) (a > \sqrt{n})

即

⌊ \log_{a}^{b} ⌋ = 1 (a > \sqrt{n})

通过这两个性质原式可以转化为如下：

\begin{aligned} \sum_{a = 2}^{n} (a \times \sum_{b = a}^{n} ⌊ \log_{a}^{b} ⌋ \times ⌈ \log_{b}^{a} ⌉) & = \sum_{a = 2}^{n} (a \times \sum_{b = a}^{n} ⌊ \log_{a}^{b} ⌋) (a > \sqrt{n}) \\ = \sum_{a = ⌊ \sqrt{n} ⌋ + 1}^{n} (a \times \sum_{b = a}^{n} ⌊ \log_{a}^{b} ⌋) \\ = \sum_{a = ⌊ \sqrt{n} ⌋ + 1}^{n} (a \times \sum_{b = a}^{n} 1) \\ = \sum_{a = ⌊ \sqrt{n} ⌋ + 1}^{n} (a \times (n - a + 1)) \\ = (n + 1) \times \sum_{a = ⌊ \sqrt{n} ⌋ + 1}^{n} a - \sum_{a = ⌊ \sqrt{n} ⌋ + 1}^{n} a^{2} \\ = (n + 1) \times \sum_{a = ⌊ \sqrt{n} ⌋ + 1}^{n} a - (\sum_{a = 1}^{n} a^{2} - \sum_{a = 1}^{⌊ \sqrt{n} ⌋} a^{2}) \\ = (n + 1) \times \frac{1}{2} \times (⌊ \sqrt{n} ⌋ + 1 + n) \times (n - (⌊ \sqrt{n} ⌋ + 1) + 1) - \\ (\frac{n (n + 1) (2 n + 1)}{6} - \frac{⌊ \sqrt{n} ⌋ \times (⌊ \sqrt{n} ⌋ + 1) \times (2 \times ⌊ \sqrt{n} ⌋ + 1)}{6}) \end{aligned}

$O(1)$ 求。

$a \le \sqrt{n}$ $O((\sqrt{n})^2) = O(n)$ $1 \times 10^8$ 的点。

$O(\sqrt{n} \log{n})$ 做法

$a$ 为底的对数函数图像：

$\lfloor \log_a^b \rfloor$ $b$ 分为如下几个区间：

[a^{1}, a^{2}), [a^{2}, a^{3}), [a^{3}, a^{4}), \dots, [a^{⌊ \log_{a}^{n} ⌋}, n]

显然对于每个区间的值域都有且只有一个值，即：

1, 2, 3, \dots, ⌊ \log_{a}^{n} ⌋

这样我们便可以以此为基础进行优化，将对应值乘上区间内值的数量在计算即可。

注意

整除

关于式子中的除法是否可以整除，可以从很多个角度来理解。

由于我们的式子是从整式推过来的，所以显然最后的结果一定是个整数，所以必定可以整除。
由于题中需要取模，所以考虑模运算一般都不考虑浮点数，故可不严谨地认为其可以整除。
通过数学严谨地证明，可以考虑将除数分解后分别讨论被除数是否存在其因数，一般通过枚举被除数某个项对除数的因子取模的值来证明。

带模除法

这部分很显然，具体做法不再赘述，将除法改为乘逆元即可。

log 精度问题

$O(n)$ 甚至更暴力的做法就需要考虑到这一点了。

很多时候我们喜欢用换底公式来简单地表示出任意一个 log 的值，但是这样的求法对于单次使用精度还可以接受，但是对于本题，会随着 n 的增大逐渐放大这样做法的精度误差~~（我模拟赛的时候就因为这个而 0pts 了）~~。

不过这个我并没有想到高效且正确的方法，类似 BitScanReverse 这种的奇淫巧计也都是 VS 里面的，OI 用不了，能想到的只有用 long double 或者 float128 之类的东西，或者干脆递归手写求 log。

就像我写的正解里面被我注释掉的那一段代码，如果那一段的思路没有假掉了的话，那么就也是 log 炸精度了。

对于取模

$n$ $long \ long$ $long \ long$ 导致 WA。

AC Code


xxxxxxxxxx
95
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3
// #include <quadmath.h>
4

5
#define PI M_PI
6
#define E M_E
7
#define npt nullptr
8
#define MOD 998244353
9

10
/******************************
11
abbr
12

13
******************************/
14

15
using namespace std;
16

17
mt19937 rnd(random_device{}());
18
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
19

20
typedef unsigned int uint;
21
typedef unsigned long long unll;
22
typedef long long ll;
23

24
#define int ll
25
#define sqrt sqrtl
26
#define floor floorl
27
#define ceil ceill
28
#define log logl
29

30
#define sqrtN (ll)(floor((long double)(sqrt(n))))
31

32
#define logg(a, b) (ll)(floor(log((long double)b) / log((long double) a))) 
33

34
int qpow(int a, int b){
35
    ll ret(1), mul(a);
36
    while(b){
37
        if(b & 1)ret = ret * mul % MOD;
38
        b >>= 1;
39
        mul = mul * mul % MOD;
40
    }
41
    return int(ret);
42
}
43

44
const int inv_2 = qpow(2, MOD - 2);
45
const int inv_6 = qpow(6, MOD - 2);
46

47
ll CalFunc(ll n){
48
    ll left = (n + 1) % MOD * (ll)inv_2 % MOD * ((sqrtN + n + 1)%MOD) % MOD * (ll(-sqrtN + n)%MOD) % MOD;
49
    ll rightl = n % MOD * ((n + 1) % MOD) % MOD * ((2 * n + 1) % MOD) % MOD * inv_6 % MOD;
50
    ll rightr = sqrtN % MOD * ((sqrtN + 1)%MOD) % MOD * ((2 * sqrtN + 1)%MOD) % MOD * (inv_6 % MOD) % MOD;
51
    ll right = (rightl - rightr + MOD) % MOD;
52
    return (left - right + MOD) % MOD;
53
}
54

55
template<typename T = int>
56
inline T read(void);
57

58
signed main(){
59
    int N = read();
60
    int ans(0ll);
61
    for(int a = 2; a * a <= N; ++a){
62
        // int tmpp(0);
63
        // for(int k = 1; k < logg(a, N); ++k){
64
        //     int tmp = (qpow(a, k + 1) - qpow(a, k) + MOD) % MOD;
65
        //     tmpp = (tmpp + tmp) % MOD; 
66
        // }
67
        // tmpp = ((N - qpow(a, logg(a, N)) + 1) % MOD + tmpp) % MOD;
68
        // ans = (ans + tmpp * a % MOD) % MOD; 
69
        ll tmp(1ll);
70
        for(int b = a; b <= N; b *= a, ++tmp){
71
            ans = (ans + (min(b * a - 1, N) - (b - 1) + MOD) % MOD * tmp % MOD * a % MOD) % MOD;
72
        }
73
    }
74
    ans = (ans + CalFunc(N)) % MOD;
75

76
    printf("%lld\n", ans);
77
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
78
    return 0;
79
}
80

81
template<typename T>
82
inline T read(void){
83
    T ret(0);
84
    short flag(1);
85
    char c = getchar();
86
    while(c != '-' && !isdigit(c))c = getchar();
87
    if(c == '-')flag = -1, c = getchar();
88
    while(isdigit(c)){
89
        ret *= 10;
90
        ret += int(c - '0');
91
        c = getchar();
92
    }
93
    ret *= flag;
94
    return ret;
95
}

UPD

update-2022_08_25 初稿

update-2022_08_25 小优化