2019银川icpc F 数论分块，技巧

题意：

给出$n$，计算
$$\sum _{a=2}^n(a\sum _{b=a}^n\lfloor f_a^{-1}(b)\rfloor \lceil f_b^{-1}(a)\rceil ),f_a(x)=a^x$$
原题如此说明$f_a^{-1}(x)$：$f_a^{-1}(x)$ is the inverse function of $f_a(x)$

Solution：

首先需要注意一个点，$f_a^{-1}(x)$是$f_a(x)$的反函数，而不是逆元，逆元是inverse element，反函数是inverse function

$f_a(b)=a^b$是个指数函数，于是反函数为对数函数$f_a^{-1}(b)=lo{g}_{a}b$

于是原式即计算
$$\sum _{a=2}^n(a\sum _{b=a}^n\lfloor lo{g}_{a}b\rfloor \lceil lo{g}_{b}a\rceil )$$
显然题意已经包含$a\le b$，于是$\lceil lo{g}_{b}a\rceil =1$，那么只需要计算
$$\sum _{a=2}^n(a\sum _{b=a}^n\lfloor lo{g}_{a}b\rfloor )$$

有关对数，今天学到一个技巧，以$\sqrt{n}$为界分块处理，这样有什么好处？

当$a>\sqrt{n}$时，枚举的$b$不超过$n$，那么就意味$\lfloor lo{g}_{a}b\rfloor =1$

于是我们先计算$a>\sqrt{n}$部分，即
$$\sum _{a=\sqrt{n}+1}^n(a\sum _{b=a}^{n}1)=\sum _{a=\sqrt{n}+1}^{n}a(n-a+1)=(n+1)\sum _{a=\sqrt{n}+1}^{n}a-\sum _{a=\sqrt{n}+1}^n{a}^2$$
第一部分等差数列求和即可，第二部分利用以下公式求和
$$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$
这个部分是$O(1)$得到的，接着计算$a\le \sqrt{n}$的部分：
$$\sum _{a=2}^n(a\sum _{b=a}^n\lfloor lo{g}_{a}b\rfloor )$$
此时$n\le 10^6$，我们考虑枚举$a$，此时如何快速求得每个$a$的值，由于出现了下取整，我们可以考虑能否进行像整除分块般的操作，一部分一部分的处理，对于对数函数$lo{g}_{a}x$，不难发现有这么几个区间段中，他们向下取整的值是一样的
$$\begin{gathered} [a,a^2-1] \\ [a^2,a^3-1] \\ .... \\ [a^k,a^{k+1}-1] \end{gathered}$$
于是我们考虑这样子对$b$的所有取值分类然后分类计算，显然最多拥有$32$次幂，于是对每个$a$，计算的次数都会在$32$以内，是可以接受的，这部分的复杂度为$O(\sqrt{n}logn)$，总复杂度为$O(\sqrt{n}logn)$

需要注意分段的时候最后一段的可能不是完整的$[a^k,a^{k+1}-1]$区间

#ifndef stdjudge
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=8e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;

ll n;

ll qm(ll x)
{
	return (x%mod+mod)%mod;
}

ll qpow(ll a,ll b)
{
	ll ret=1,base=a;
	while(b)
	{
		if(b&1) ret=ret*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ret;
}

ll inv(ll x){return qpow(x,mod-2);}

ll f(ll x)
{
	return qm(x)*qm(x+1)%mod*qm(2*qm(x)%mod+1)%mod*inv(6)%mod;
}

int main()
{
	#ifdef stdjudge
		freopen("in.txt","r",stdin);
	#endif
	cin>>n;
	ll ans=0,limit=1;
	for(ll i=2;i*i<=n;i++)
	{
		limit++;
		ll last=i,now=i*i,val=1;
		while(1)
		{
			bool flag=(now-1>=n); now=min(now,n);
			ans=(ans+qm(i)*qm(val)%mod*qm(now-last+(flag))%mod)%mod;
			last=now; now*=i; val++;
			if(flag) break;
		}
	}
	cout<<qm(ans+qm(n+1)*qm(limit+n+1)%mod*qm(n-limit)%mod*inv(2)%mod-qm(f(n)-f(limit)))<<'\n';
	return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65